package alice.exercise.leetcode.simple;

import alice.exercise.leetcode.entity.ListNode;
import alice.exercise.leetcode.entity.TreeNode;

import java.nio.charset.StandardCharsets;
import java.time.LocalDate;
import java.time.format.TextStyle;
import java.util.*;
import java.util.concurrent.CompletableFuture;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;

/**
 * {@link MainTest}
 *
 * @author Alice
 * @since 2023-02-06 星期一 9:23
 */
class Solution {
  private static final int MOD = 1000000007;
  private static final int[][] HOURS = new int[][]{new int[]{0}, new int[]{1, 2, 4, 8}, new int[]{3, 5, 6, 9, 10}, new int[]{7, 11}};
  private static final int[][] MINUTES = new int[][]{
    new int[]{0},
    new int[]{1, 2, 4, 8, 16, 32},
    new int[]{3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48},
    new int[]{7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56},
    new int[]{15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58},
    new int[]{31, 47, 55, 59}
  };
  private static final char[] HEX_ELEMENTS = new char[]{'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
  private static final boolean[] DIGITAL_OR_ALPHABET;
  private static final String[] MORSE_DICT = new String[]{".-", "-...", "-.-.", "-..", ".", "..-.", "--.",
    "....", "..", ".---", "-.-", ".-..", "--", "-.",
    "---", ".--.", "--.-", ".-.", "...", "-",
    "..-", "...-", ".--", "-..-", "-.--", "--.."};
  private static final int[][] MORSE_DICT_PLUS = new int[][]{
    new int[]{0x1, 2},
    new int[]{0x8, 4},
    new int[]{0xa, 4},
    new int[]{0x4, 3},
    new int[]{0x0, 1},
    new int[]{0x2, 4},
    new int[]{0x6, 3},
    new int[]{0x0, 4},
    new int[]{0x0, 2},
    new int[]{0x7, 4},
    new int[]{0x5, 3},
    new int[]{0x4, 4},
    new int[]{0x3, 2},
    new int[]{0x2, 2},
    new int[]{0x7, 3},
    new int[]{0x6, 4},
    new int[]{0xd, 4},
    new int[]{0x2, 3},
    new int[]{0x0, 3},
    new int[]{0x1, 1},
    new int[]{0x1, 3},
    new int[]{0x1, 4},
    new int[]{0x3, 3},
    new int[]{0x9, 4},
    new int[]{0xb, 4},
    new int[]{0xc, 4}
  };
  private static final int[] MONTHS = new int[]{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  private static final int[] TRIBONACCI_CACHE = new int[]{0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705,
    3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770, 8646064, 15902591,
    29249425, 53798080, 98950096, 181997601, 334745777, 615693474, 1132436852, 2082876103};

  private int preEle = -1;
  private int minimumDifference = Integer.MAX_VALUE;

  static {
    DIGITAL_OR_ALPHABET = new boolean[128];
    for (int i = '0'; i <= '9'; i++) {
      DIGITAL_OR_ALPHABET[i] = true;
    }
    for (int i = 'A'; i <= 'Z'; i++) {
      DIGITAL_OR_ALPHABET[i] = true;
    }
    for (int i = 'a'; i <= 'z'; i++) {
      DIGITAL_OR_ALPHABET[i] = true;
    }
  }

  // TODO 1758. 生成交替二进制字符串的最少操作数
  public int minOperations(String s) {
    int len = s.length(), sum = 0;
    boolean b = s.charAt(0) == '1';
    char c;
    for (int i = 1; i < len; i++) {
      c = s.charAt(i);
      if (b && c == '1') {
        sum++;
        b = false;
      } else if (!b && c == '0') {
        sum++;
        b = true;
      } else {
        b = c == '1';
      }
    }
    return sum;
  }

  public int minOperations1(String s) {
    int len = s.length(), sum = 0;
    boolean b = s.charAt(0) == '0';
    char c;
    for (int i = 1; i < len; i++) {
      c = s.charAt(i);
      if (b && c == '0') {
        sum++;
        b = false;
      } else if (!b && c == '1') {
        sum++;
        b = true;
      } else {
        b = c == '0';
      }
    }
    return sum;
  }

  // 1437. 是否所有 1 都至少相隔 k 个元素
  public boolean kLengthApart(int[] nums, int k) {
    int lastOneIndex = -1;
    for (int i = 0; i < nums.length; i++) {
      if (nums[i] == 1) {
        if (lastOneIndex > -1 && (i - lastOneIndex) <= k) {
          return false;
        }
        lastOneIndex = i;
      }
    }
    return true;
  }

  // 999. 可以被一步捕获的棋子数
  public int numRookCaptures(char[][] board) {
    int x = 0, y = 0, res = 0;
    flag:
    for (x = 0; x < 8; x++) {
      for (y = 0; y < 8; y++) {
        if (board[x][y] == 'R') {
          break flag;
        }
      }
    }
    for (int i = x + 1; i < 8; i++) {
      if (board[i][y] == 'B') {
        break;
      }
      if (board[i][y] == 'p') {
        res++;
        break;
      }
    }
    for (int i = x - 1; i >= 0; i--) {
      if (board[i][y] == 'B') {
        break;
      }
      if (board[i][y] == 'p') {
        res++;
        break;
      }
    }
    for (int j = y - 1; j >= 0; j--) {
      if (board[x][j] == 'B') {
        break;
      }
      if (board[x][j] == 'p') {
        res++;
        break;
      }
    }
    for (int j = y + 1; j < 8; j++) {
      if (board[x][j] == 'B') {
        break;
      }
      if (board[x][j] == 'p') {
        res++;
        break;
      }
    }
    return res;
  }

  // 1021. 删除最外层的括号
  public String removeOuterParentheses(String s) {
    StringBuilder result = new StringBuilder();
    int stack = 0, len = s.length();
    char c;
    for (int i = 0; i < len; i++) {
      c = s.charAt(i);
      if (c == ')') {
        stack--;
      }
      if (stack > 0) {
        result.append(c);
      }
      if (c == '(') {
        stack++;
      }
    }
    return result.toString();
  }

  // 2682. 找出转圈游戏输家
  public int[] circularGameLosers(int n, int k) {
    int[] bucket = new int[51];
    int pre = 1, i = 0;
    do {
      pre = (pre + i * k) % n;
      if (pre == 0) {
        pre = n;
      }
      i++;
    } while (++bucket[pre] <= 1);
    int[] res = new int[n];
    int count = 0, index = 0;
    for (int j = 2; j <= n; j++) {
      if (bucket[j] == 0) {
        count++;
        res[index++] = j;
      }
    }
    return Arrays.copyOf(res, count);
  }

  // 2670. 找出不同元素数目差数组
  public int[] distinctDifferenceArray(int[] nums) {
    int[] arr1 = new int[51];
    int[] arr2 = new int[51];
    int left = 0, right = 0;
    for (int n : nums) {
      if (arr2[n]++ == 0) {
        right++;
      }
    }
    int len = nums.length;
    int[] res = new int[len];
    for (int i = 0; i < len; i++) {
      if (arr1[nums[i]]++ == 0) {
        left++;
      }
      if (--arr2[nums[i]] == 0) {
        right--;
      }
      res[i] = left - right;
    }
    return res;
  }

  // 2696. 删除子串后的字符串最小长度
  public int minLength(String s) {
    LinkedList<Character> list = new LinkedList<>();
    int len = s.length();
    char c;
    for (int i = 0; i < len; i++) {
      c = s.charAt(i);
      if (c == 'B' && !list.isEmpty() && list.peekLast() == 'A') {
        list.removeLast();
      } else if (c == 'D' && !list.isEmpty() && list.peekLast() == 'C') {
        list.removeLast();
      } else {
        list.add(c);
      }
    }
    return list.size();
  }

  // 1742. 盒子中小球的最大数量
  public int countBalls(int lowLimit, int highLimit) {
    int len = highLimit - lowLimit + 1;
    int[] cache = new int[len];
    cache[0] = eachSum(lowLimit);
    int max = -1, index;
    int[] bucket = new int[46];
    for (int i = lowLimit + 1; i <= highLimit; i++) {
      index = i - lowLimit;
      cache[index] = (i % 10 == 0) ? eachSum(i) : (cache[index - 1] + 1);
    }
    for (int i = 0; i < len; i++) {
      if (++bucket[cache[i]] > max) {
        max = bucket[cache[i]];
      }
    }
    return max;
  }

  private int eachSum(int n) {
    int res = 0;
    while (n > 0) {
      res += (n % 10);
      n /= 10;
    }
    return res;
  }

  // 1652. 拆炸弹
  public int[] decrypt(int[] code, int k) {
    int len = code.length;
    int[] res = new int[len];
    if (k == 0) {
      return res;
    }
    if (k > 0) {
      int index = 1;
      for (int i = 0; i < k; i++) {
        res[0] += code[index];
        index = (index + 1) % len;
      }
      for (int i = 1; i < len; i++) {
        res[i] = res[i - 1] + code[index] - code[i];
        index = (index + 1) % len;
      }
    } else {
      int index = len + k;
      for (int i = index; i < len; i++) {
        res[0] += code[i];
      }
      for (int i = 1; i < len; i++) {
        res[i] = res[i - 1] + code[i - 1] - code[index];
        index = (index + 1) % len;
      }
    }
    return res;
  }

  // 1022. 从根到叶的二进制数之和
  public int sumRootToLeaf(TreeNode root) {
    return calSumRootToLeaf(root, 0);
  }

  private int calSumRootToLeaf(TreeNode root, int sum) {
    if (root == null) {
      return 0;
    }
    sum = (sum << 1) | root.val;
    if (root.left == null && root.right == null) {
      return sum;
    }
    return calSumRootToLeaf(root.left, sum) + calSumRootToLeaf(root.right, sum);
  }

  // 1331. 数组序号转换
  public int[] arrayRankTransform(int[] arr) {
    int len = arr.length;
    int[] bak = new int[len], res = new int[len];
    System.arraycopy(arr, 0, bak, 0, len);
    Arrays.sort(bak);
    Map<Integer, Integer> map = new HashMap<>();
    for (int x : bak) {
      if (!map.containsKey(x)) {
        map.put(x, map.size() + 1);
      }
    }
    for (int i = 0; i < len; i++) {
      res[i] = map.get(arr[i]);
    }
    return res;
  }

  // 2073. 买票需要的时间
  public int timeRequiredToBuy(int[] tickets, int k) {
    int len = tickets.length, res = 0;
    for (int i = 0; i < len; i++) {
      if (i <= k) {
        res += Math.min(tickets[i], tickets[k]);
      } else {
        res += Math.min(tickets[i], tickets[k] - 1);
      }
    }
    return res;
  }

  // 2164. 对奇偶下标分别排序
  public int[] sortEvenOdd(int[] nums) {
    int len = nums.length;
    if (len <= 2) {
      return nums;
    }
    int oddCount = len >> 1, evenCount = (len + 1) >> 1;
    int[] arr = new int[len];
    for (int i = 0; i < evenCount; i++) {
      arr[i] = nums[i << 1];
    }
    for (int i = 0; i < oddCount; i++) {
      arr[i + evenCount] = nums[(i << 1) | 1];
    }
    Arrays.sort(arr, 0, evenCount);
    Arrays.sort(arr, evenCount, len);
    Arrays.fill(nums, 0);
    int evenIndex = 0, oddIndex = 0;
    for (int i = 0; i < len; i++) {
      if ((i & 1) == 0) {
        nums[i] = arr[evenIndex];
        evenIndex++;
      } else {
        nums[i] = arr[len - 1 - oddIndex];
        oddIndex++;
      }
    }
    return nums;
  }

  // 2423. 删除字符使频率相同
  public boolean equalFrequency(String word) {
    int[] bucket = new int[26];
    int len = word.length();
    for (int i = 0; i < len; i++) {
      bucket[word.charAt(i) - 'a']++;
    }
    for (int i = 0; i < 26; i++) {
      if (bucket[i] == 0) {
        continue;
      }
      bucket[i]--;
      if (sameCount(bucket)) {
        return true;
      }
      bucket[i]++;
    }
    return false;
  }

  private boolean sameCount(int[] nums) {
    int target = -1;
    for (int i = 0; i < 26; i++) {
      if (nums[i] > 0) {
        if (target == -1) {
          target = nums[i];
        } else if (nums[i] != target) {
          return false;
        }
      }
    }
    return true;
  }

  // 2540. 最小公共值
  public int getCommon(int[] nums1, int[] nums2) {
    int len1 = nums1.length, len2 = nums2.length;
    int i = 0, j = 0;
    while (i < len1 && j < len2) {
      if (nums1[i] < nums2[j]) {
        i++;
        continue;
      }
      if (nums1[i] > nums2[j]) {
        j++;
        continue;
      }
      return nums1[i];
    }
    return -1;
  }

  // 2446. 判断两个事件是否存在冲突
  public boolean haveConflict(String[] event1, String[] event2) {
    return event1[0].compareTo(event2[1]) <= 0 && event2[0].compareTo(event1[1]) <= 0;
  }

  // 1539. 第 k 个缺失的正整数
  public int findKthPositive1(int[] arr, int k) {
    int len = arr.length, index = 0;
    for (int i = 1, i1 = 0; true; i++) {
      if (i1 >= len || i != arr[i1]) {
        if (++index == k) {
          return i;
        }
      } else {
        i1++;
      }
    }
  }

  public int findKthPositive(int[] arr, int k) {
    for (int n : arr) {
      if (n <= k) {
        k++;
      }
    }
    return k;
  }

  // 1523. 在区间范围内统计奇数数目
  public int countOdds1(int low, int high) {
    boolean flag1 = (low & 1) == 1, flag2 = (high & 1) == 1;
    int diff = high - low;
    if (flag1 != flag2) {
      return (diff + 1) >> 1;
    } else if (flag1) {
      return 1 + (diff >> 1);
    } else {
      return diff >> 1;
    }
  }

  public int countOdds(int low, int high) {
    return ((high + 1) >> 1) - (low >> 1);
  }

  // 2062. 统计字符串中的元音子字符串
  public int countVowelSubstrings(String word) {
    int[] bitDict = new int[26];
    bitDict[0] = 1;
    bitDict['e' - 'a'] = 2;
    bitDict['i' - 'a'] = 4;
    bitDict['o' - 'a'] = 8;
    bitDict['u' - 'a'] = 16;
    int len = word.length();
    int[] bit = new int[len];
    for (int i = 0; i < len; i++) {
      bit[i] = bitDict[word.charAt(i) - 'a'];
    }
    int res = 0, bitSum;
    for (int i = 0; i < len - 4; i++) {
      bitSum = 0;
      for (int j = i; j < len; j++) {
        if (bit[j] == 0) {
          break;
        }
        bitSum |= bit[j];
        if (bitSum == 31) {
          res++;
        }
      }
    }
    return res;
  }

  // 2215. 找出两数组的不同
  public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
    int[] bucket = new int[2002];
    int offset = 1000;
    for (int n : nums1) {
      bucket[n + offset] |= 1;
    }
    for (int n : nums2) {
      bucket[n + offset] |= 2;
    }
    List<List<Integer>> res = new ArrayList<>(2);
    List<Integer> one_two = new ArrayList<>();
    List<Integer> two_one = new ArrayList<>();
    res.add(one_two);
    res.add(two_one);
    for (int i = 0; i < 2002; i++) {
      if (bucket[i] == 1) {
        one_two.add(i - offset);
      } else if (bucket[i] == 2) {
        two_one.add(i - offset);
      }
    }
    return res;
  }

  // 2200. 找出数组中的所有 K 近邻下标
  public List<Integer> findKDistantIndices(int[] nums, int key, int k) {
    int len = nums.length, lastEnd = 0;
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < len; i++) {
      if (nums[i] == key) {
        for (int j = Math.max(i - k, lastEnd); j <= Math.min(i + k, len - 1); j++) {
          list.add(j);
        }
        lastEnd = i + k + 1;
      }
    }
    return list;
  }

  // 2032. 至少在两个数组中出现的值
  public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {
    int[] bucket = new int[101];
    for (int n : nums1) {
      bucket[n] |= 1;
    }
    for (int n : nums2) {
      bucket[n] |= 2;
    }
    for (int n : nums3) {
      bucket[n] |= 4;
    }
    List<Integer> list = new ArrayList<>();
    for (int i = 1; i < 101; i++) {
      if ((bucket[i] & bucket[i] - 1) != 0) {
        list.add(i);
      }
    }
    return list;
  }

  // 1854. 人口最多的年份
  public int maximumPopulation(int[][] logs) {
    int[] amount = new int[101];
    int offset = 1950;
    for (int[] log : logs) {
      amount[log[0] - offset]++;
      amount[log[1] - offset]--;
    }
    int max = 0, start = 0, sum = 0;
    for (int i = 1; i < 101; i++) {
      if ((sum += amount[i]) > max) {
        max = sum;
        start = i;
      }
    }
    return start + 1950;
  }

  // 1608. 特殊数组的特征值
  public int specialArray(int[] nums) {
    int[] bucket = new int[1001];
    for (int n : nums) {
      bucket[n]++;
    }
    int len = nums.length, preSum = 0, count, pre = -1;
    for (int i = 0; i < 1001; i++) {
      if (bucket[i] == 0) {
        continue;
      }
      // 大于等于 i 的有(len - preSum)个
      if ((count = len - preSum) <= i && count > pre) {
        return count;
      }
      preSum += bucket[i];
      pre = i;
    }
    return -1;
  }

  // 2148. 元素计数
  public int countElements(int[] nums) {
    int len = nums.length;
    int max = nums[0], min = nums[0], maxCount = 1, minCount = 1;
    for (int i = 1; i < len; i++) {
      if (nums[i] > max) {
        max = nums[i];
        maxCount = 1;
      } else if (nums[i] == max) {
        maxCount++;
      }
      if (nums[i] < min) {
        min = nums[i];
        minCount = 1;
      } else if (nums[i] == min) {
        minCount++;
      }
    }
    return Math.max(0, len - maxCount - minCount);
  }

  // 2404. 出现最频繁的偶数元素
  public int mostFrequentEven(int[] nums) {
    int[] bucket = new int[50001];
    int maxCount = 0, index = -1, currCount, currIndex;
    for (int n : nums) {
      if ((n & 1) == 1) {
        continue;
      }
      currIndex = n >> 1;
      currCount = ++bucket[currIndex];
      if (currCount < maxCount) {
        continue;
      }
      if (currCount > maxCount || currIndex < index) {
        maxCount = currCount;
        index = currIndex;
      }
    }
    return index << 1;
  }

  // 2129. 将标题首字母大写
  public String capitalizeTitle(String title) {
    String[] words = title.split(" ");
    StringBuilder builder = new StringBuilder();
    int len;
    boolean flag = false;
    for (String word : words) {
      if (flag) {
        builder.append(' ');
      }
      len = word.length();
      if (len > 2) {
        builder.append((char) ((word.charAt(0) & 0x1f) | (1 << 6)));
        for (int i = 1; i < len; i++) {
          builder.append((char) (word.charAt(i) | 0x20));
        }
      } else {
        for (int i = 0; i < len; i++) {
          builder.append((char) (word.charAt(i) | 0x20));
        }
      }
      flag = true;
    }
    return builder.toString();
  }

  // 1518. 换水问题
  public int numWaterBottles(int numBottles, int numExchange) {
    int res = numBottles, curr, other;
    while (numBottles >= numExchange) {
      curr = numBottles / numExchange;
      other = numBottles % numExchange;
      numBottles = curr + other;
      res += curr;
    }
    return res;
  }

  // 1252. 奇数值单元格的数目
  public int oddCells1(int m, int n, int[][] indices) {
    int[] rows = new int[m];
    int[] cols = new int[n];
    int res = 0;
    for (int[] arr : indices) {
      rows[arr[0]]++;
      cols[arr[1]]++;
    }
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (((rows[i] + cols[j]) & 1) == 1) {
          res++;
        }
      }
    }
    return res;
  }

  public int oddCells(int m, int n, int[][] indices) {
    int[] rows = new int[m];
    int[] cols = new int[n];
    for (int[] arr : indices) {
      rows[arr[0]]++;
      cols[arr[1]]++;
    }
    int rowsOdd = 0, colsOdd = 0;
    for (int row : rows) {
      if ((row & 1) == 1) {
        rowsOdd++;
      }
    }
    for (int col : cols) {
      if ((col & 1) == 1) {
        colsOdd++;
      }
    }
    return rowsOdd * (n - colsOdd) + (m - rowsOdd) * colsOdd;
  }

  // 1323. 6 和 9 组成的最大数字
  public int maximum69Number(int num) {
    int[] arr = new int[4];
    int i = 4;
    while (num > 0) {
      arr[--i] = num % 10;
      num /= 10;
    }
    int res = 0;
    boolean found = false;
    while (i < 4) {
      if (!found && arr[i] == 6) {
        arr[i] = 9;
        found = true;
      }
      res += arr[i] * Math.pow(10, 3 - i);
      i++;
    }
    return res;
  }

  // 1356. 根据数字二进制下 1 的数目排序
  public int[] sortByBits(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {
      arr[i] = Integer.bitCount(arr[i]) * 100000 + arr[i];
    }
    Arrays.sort(arr);
    for (int i = 0; i < n; i++) {
      arr[i] %= 100000;
    }
    return arr;
  }

  // 1380. 矩阵中的幸运数
  public List<Integer> luckyNumbers(int[][] matrix) {
    Set<Integer> minSet = new HashSet<>();
    int n = matrix[0].length, x;
    List<Integer> res = new ArrayList<>();
    for (int[] arr : matrix) {
      x = 100001;
      for (int j = 0; j < n; j++) {
        x = Math.min(x, arr[j]);
      }
      minSet.add(x);
    }
    for (int j = 0; j < n; j++) {
      x = 0;
      for (int[] arr : matrix) {
        x = Math.max(x, arr[j]);
      }
      if (minSet.contains(x)) {
        res.add(x);
      }
    }
    return res;
  }

  // 1417. 重新格式化字符串
  public String reformat(String s) {
    int n = s.length();
    char[] digitArray = new char[n];
    char[] alphabetArray = new char[n];
    char[] res = new char[n];
    int n1 = 0, n2 = 0, i = 0, index = 0;
    char c;
    for (int k = 0; k < n; k++) {
      if (Character.isDigit(c = s.charAt(k))) {
        digitArray[n1++] = c;
      } else {
        alphabetArray[n2++] = c;
      }
    }
    if (Math.abs(n1 - n2) > 1) {
      return "";
    }
    if (n1 > n2) {
      for (; i < n2; i++) {
        res[index++] = digitArray[i];
        res[index++] = alphabetArray[i];
      }
      res[index] = digitArray[i];
    } else {
      for (; i < n1; i++) {
        res[index++] = alphabetArray[i];
        res[index++] = digitArray[i];
      }
      if (i < n2) {
        res[index] = alphabetArray[i];
      }
    }
    return new String(res);
  }

  // 1185. 一周中的第几天
  public String dayOfTheWeek(int day, int month, int year) {
    return LocalDate.of(year, month, day).getDayOfWeek().getDisplayName(TextStyle.FULL, Locale.ENGLISH);
  }

  // 1217. 玩筹码
  public int minCostToMoveChips(int[] position) {
    int odd = 0, even = 0;
    for (int n : position) {
      if ((n & 1) == 0) {
        even++;
      } else {
        odd++;
      }
    }
    return Math.min(odd, even);
  }

  // 1200. 最小绝对差
  public List<List<Integer>> minimumAbsDifference(int[] arr) {
    Map<Integer, List<List<Integer>>> res = new HashMap<>();
    Arrays.sort(arr);
    int n = arr.length, min = 2000001;
    for (int i = 1; i < n; i++) {
      int diff = arr[i] - arr[i - 1];
      if (diff == min) {
        res.get(diff).add(Arrays.asList(arr[i - 1], arr[i]));
      } else if (diff < min) {
        min = diff;
        List<List<Integer>> list = new ArrayList<>();
        list.add(Arrays.asList(arr[i - 1], arr[i]));
        res.put(diff, list);
      }
    }
    return res.get(min);
  }

  // 1189. “气球” 的最大数量
  public int maxNumberOfBalloons(String text) {
    int n = text.length();
    int[] arr = new int[26];
    for (int i = 0; i < n; i++) {
      arr[text.charAt(i) - 'a']++;
    }
    int res = arr[0];
    res = Math.min(res, arr[1]);
    res = Math.min(res, arr[11] >> 1);
    res = Math.min(res, arr[13]);
    return Math.min(res, arr[14] >> 1);
  }

  // 1207. 独一无二的出现次数
  public boolean uniqueOccurrences(int[] arr) {
    int[] times = new int[1001];
    Map<Integer, Integer> timesMap = new HashMap<>();
    for (int n : arr) {
      timesMap.put(n, timesMap.getOrDefault(n, 0) + 1);
    }
    Collection<Integer> values = timesMap.values();
    for (Integer value : values) {
      if (times[value]++ > 0) {
        return false;
      }
    }
    return true;
  }

  // 1232. 缀点成线
  public boolean checkStraightLine(int[][] coordinates) {
    int n = coordinates.length;
    int divider = coordinates[1][0] - coordinates[0][0];
    if (divider == 0) {
      for (int i = 2; i < n; i++) {
        if (coordinates[i][0] != coordinates[0][0]) {
          return false;
        }
      }
    } else {
      double k = ((double) coordinates[1][1] - coordinates[0][1]) / divider, e = 1e-5;
      for (int i = 2; i < n; i++) {
        if (Math.abs(((double) coordinates[i][1] - coordinates[0][1]) / (coordinates[i][0] - coordinates[0][0]) - k) > e) {
          return false;
        }
      }
    }
    return true;
  }

  // 2399. 检查相同字母间的距离
  public boolean checkDistances(String s, int[] distance) {
    int[] arr = new int[26];
    Arrays.fill(arr, -1);
    int n = s.length(), index;
    for (int i = 0; i < n; i++) {
      index = s.charAt(i) - 'a';
      if (arr[index] == -1) {
        arr[index] = i;
      } else {
        arr[index] = i - arr[index] - 1;
      }
    }
    for (int i = 0; i < 26; i++) {
      if (arr[i] != -1 && distance[i] != arr[i]) {
        return false;
      }
    }
    return true;
  }

  // 1399. 统计最大组的数目
  public int countLargestGroup(int n) {
    int[] bucket = new int[37];
    int max = 0;
    for (int i = 1; i <= n; i++) {
      int key = calCountLargestGroup(i);
      bucket[key]++;
      max = Math.max(max, bucket[key]);
    }
    int res = 0;
    for (int i = 1; i < 37; i++) {
      if (bucket[i] == max) {
        res++;
      }
    }
    return res;
  }

  private int calCountLargestGroup(int n) {
    int x = 0;
    while (n > 0) {
      x += n % 10;
      n /= 10;
    }
    return x;
  }

  // 1394. 找出数组中的幸运数
  public int findLucky(int[] arr) {
    int[] bucket = new int[501];
    for (int i : arr) {
      bucket[i]++;
    }
    for (int i = 500; i > 0; i--) {
      if (bucket[i] == i) {
        return i;
      }
    }
    return -1;
  }

  // 1184. 公交站间的距离
  public int distanceBetweenBusStops(int[] distance, int start, int destination) {
    int n = distance.length, clockwise = 0, counterclockwise = 0;
    int i = start;
    while (true) {
      clockwise += distance[i];
      if ((i = (i + 1) % n) == destination) {
        break;
      }
    }
    while (true) {
      counterclockwise += distance[i];
      if ((i = (i + 1) % n) == start) {
        break;
      }
    }
    return Math.min(clockwise, counterclockwise);
  }

  // 942. 增减字符串匹配
  public int[] diStringMatch(String s) {
    int len = s.length(), i = 0, j = len;
    int[] arr = new int[j + 1];
    for (int k = 0; k < len; k++) {
      if (s.charAt(k) == 'I') {
        arr[k] = i++;
      } else {
        arr[k] = j--;
      }
    }
    arr[len] = i;
    return arr;
  }

  // 1175. 质数排列
  public int numPrimeArrangements(int n) {
    int mod = 1000000007;
    int[] arr = new int[]{0, 0, 1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25};
    long x = 1;
    for (int i = arr[n]; i > 1; i--) {
      x = (x * i) % mod;
    }
    for (int i = n - arr[n]; i > 1; i--) {
      x = (x * i) % mod;
    }
    return (int) (x % 1000000007);
  }

  // 944. 删列造序
  public int minDeletionSize(String[] strs) {
    int len = strs[0].length(), del = 0;
    boolean[] flag = new boolean[len];
    String pre = null;
    for (String s : strs) {
      if (pre != null) {
        for (int i = 0; i < len; i++) {
          if (flag[i]) {
            continue;
          }
          if (pre.charAt(i) - s.charAt(i) > 0) {
            del++;
            flag[i] = true;
          }
        }
      }
      pre = s;
    }
    return del;
  }

  // 961. 在长度 2N 的数组中找出重复 N 次的元素
  public int repeatedNTimes(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) {
      if (!set.add(n)) {
        return n;
      }
    }
    return -1;
  }

  // 2475. 数组中不等三元组的数目
  public int unequalTriplets1(int[] nums) {
    int[] bucket = new int[1001];
    for (int n : nums) {
      bucket[n]++;
    }
    int res = 0, left = 0, right = nums.length;
    for (int i = 0; i < 1001; i++) {
      right -= bucket[i];
      res += left * bucket[i] * right;
      left += bucket[i];
    }
    return res;
  }

  public int unequalTriplets(int[] nums) {
    int[] bucket = new int[1001];
    for (int n : nums) {
      bucket[n]++;
    }
    int len = nums.length;
    long total = (long) len * (len - 1) * (len - 2) / 6;
    long condition1 = 0, condition2 = 0;
    for (int i = 0; i < 1001; i++) {
      if (bucket[i] >= 3) {
        condition1 += (long) bucket[i] * (bucket[i] - 1) * (bucket[i] - 2) / 6;
      }
      if (bucket[i] >= 2) {
        condition2 += (long) bucket[i] * (bucket[i] - 1) * (len - bucket[i]) / 2;
      }
    }
    return ((int) (total - condition1 - condition2));
  }

  // 2490. 回环句
  public boolean isCircularSentence(String sentence) {
    int n = sentence.length();
    if (sentence.charAt(0) != sentence.charAt(n - 1)) {
      return false;
    }
    for (int i = 1; i < n - 1; i++) {
      if (sentence.charAt(i) == ' ') {
        if (sentence.charAt(i - 1) != sentence.charAt(i + 1)) {
          return false;
        }
      }
    }
    return true;
  }

  // 2451. 差值数组不同的字符串
  public String oddString(String[] words) {
    int len = words.length, n = words[0].length();
    int[] arr1 = null, arr2 = null;
    int i1 = -1, i2 = -1;
    boolean sameFound = false;
    for (int i = 0; i < len; i++) {
      int[] ints = new int[n - 1];
      for (int j = 0; j < n - 1; j++) {
        ints[j] = words[i].charAt(j + 1) - words[i].charAt(j);
      }
      if (arr1 == null) {
        arr1 = ints;
        i1 = i;
      } else if (arr2 == null) {
        if (Arrays.equals(ints, arr1)) {
          sameFound = true;
          continue;
        }
        if (sameFound) {
          return words[i];
        }
        arr2 = ints;
        i2 = i;
      } else {
        return Arrays.equals(arr1, ints) ? words[i2] : words[i1];
      }
    }
    return null;
  }

  // 1678. 设计 Goal 解析器
  public String interpret(String command) {
    StringBuilder builder = new StringBuilder();
    int n = command.length(), i = 0;
    while (i < n) {
      if (command.charAt(i) == 'G') {
        builder.append('G');
        i++;
      } else if (command.charAt(i + 1) == ')') {
        builder.append('o');
        i += 2;
      } else {
        builder.append("al");
        i += 4;
      }
    }
    return builder.toString();
  }

  // 2535. 数组元素和与数字和的绝对差
  public int differenceOfSum(int[] nums) {
    int res = 0;
    for (int n : nums) {
      res += calDifferenceOfSum(n);
    }
    return res;
  }

  private int calDifferenceOfSum(int n) {
    int x = 0, unit = 10;
    do {
      n /= 10;
      x += (n % 10) * (unit - 1);
      unit *= 10;
    } while (n > 0);
    return x;
  }

  // 1832. 判断句子是否为全字母句
  public boolean checkIfPangram(String sentence) {
    int n = sentence.length(), x = 0;
    for (int i = 0; i < n; i++) {
      x |= 1 << (sentence.charAt(i) - 'a');
    }
    return x == 0x3ffffff;
  }

  // 1773. 统计匹配检索规则的物品数量
  public int countMatches(List<List<String>> items, String ruleKey, String ruleValue) {
    Map<String, Integer> indexMap = new HashMap<>(3);
    indexMap.put("type", 0);
    indexMap.put("color", 1);
    indexMap.put("name", 2);
    return (int) items.stream().filter(list -> ruleValue.equals(list.get(indexMap.get(ruleKey)))).count();
  }

  // 2367. 算术三元组的数目
  public int arithmeticTriplets(int[] nums, int diff) {
    int[] bucket = new int[201];
    for (int n : nums) {
      bucket[n]++;
    }
    int res = 0, doubleDiff = diff << 1;
    for (int n : nums) {
      if (n + diff < 201 && bucket[n + diff] > 0 && n + doubleDiff < 201 && bucket[n + doubleDiff] > 0) {
        res++;
      }
    }
    return res;
  }

  // 2562. 找出数组的串联值
  public long findTheArrayConcVal(int[] nums) {
    int i = 0, j = nums.length - 1;
    long x = 0;
    while (i < j) {
      x += concVal(nums[i++], nums[j--]);
    }
    if (i == j) {
      x += nums[i];
    }
    return x;
  }

  private int concVal(int x, int y) {
    return x * (int) Math.pow(10, (int) Math.log10(y) + 1) + y;
  }

  // 2574. 左右元素和的差值
  public int[] leftRigthDifference(int[] nums) {
    int n = nums.length;
    int[] sumArr = new int[n];
    sumArr[0] = nums[0];
    for (int i = 1; i < n; i++) {
      sumArr[i] = sumArr[i - 1] + nums[i];
    }
    int sum = sumArr[n - 1];
    int[] res = new int[n];
    for (int i = 0; i < n; i++) {
      res[i] = Math.abs(sum + nums[i] - sumArr[i] * 2);
    }
    return res;
  }

  // 2418. 按身高排序
  public String[] sortPeople(String[] names, int[] heights) {
    int n = names.length;
    int[][] arr = new int[n][2];
    for (int i = 0; i < n; i++) {
      arr[i] = new int[]{heights[i], i};
    }
    Arrays.sort(arr, Comparator.comparingInt(p -> -p[0]));
    String[] res = new String[n];
    for (int i = 0; i < n; i++) {
      res[i] = names[arr[i][1]];
    }
    return res;
  }

  // 2248. 多个数组求交集
  public List<Integer> intersection(int[][] nums) {
    List<Integer> list = new ArrayList<>();
    int[] bucket = new int[1001];
    for (int[] item : nums) {
      for (int i : item) {
        bucket[i]++;
      }
    }
    int n = nums.length;
    for (int i = 1; i < 1001; i++) {
      if (bucket[i] >= n) {
        list.add(i);
      }
    }
    return list;
  }

  // 2591. 将钱分给最多的儿童
  public int distMoney(int money, int children) {
    int remain = money - children;
    if (remain < 0) {
      return -1;
    }
    int a = remain / 7;
    int b = remain % 7;
    int diff = children - a;
    if (diff < 0) {
      return children - 1;
    } else if (diff > 0) {
      if (diff == 1 && b == 3) {
        return a - 1;
      } else {
        return a;
      }
    } else {
      if (b > 0) {
        return a - 1;
      } else {
        return a;
      }
    }
  }

  // 2595. 奇偶位数
  public int[] evenOddBit(int n) {
    int even = 0, odd = 0;
    boolean isEven = true;
    while (n > 0) {
      if ((n & 1) == 1) {
        if (isEven) {
          even++;
        } else {
          odd++;
        }
      }
      n >>= 1;
      isEven = !isEven;
    }
    return new int[]{even, odd};
  }

  // 1137. 第 N 个泰波那契数
  public int tribonacci(int n) {
    return TRIBONACCI_CACHE[n];
  }

  // 1128. 等价多米诺骨牌对的数量
  public int numEquivDominoPairs(int[][] dominoes) {
    int[] cache = new int[100];
    int res = 0, val;
    for (int[] domino : dominoes) {
      val = domino[0] < domino[1] ? domino[0] * 10 + domino[1] : domino[1] * 10 + domino[0];
      res += cache[val]++;
    }
    return res;
  }

  // 1160. 拼写单词
  public int countCharacters(String[] words, String chars) {
    int[] mine = new int[26];
    int n = chars.length();
    for (int i = 0; i < n; i++) {
      mine[chars.charAt(i) - 'a']++;
    }
    int[] tmp;
    int total = 0;
    flag:
    for (String word : words) {
      n = word.length();
      tmp = new int[26];
      for (int i = 0; i < n; i++) {
        tmp[word.charAt(i) - 'a']++;
      }
      for (int i = 0; i < 26; i++) {
        if (tmp[i] <= 0) {
          continue;
        }
        if (tmp[i] > mine[i]) {
          continue flag;
        }
      }
      total += n;
    }
    return total;
  }

  // 1122. 数组的相对排序
  public int[] relativeSortArray1(int[] arr1, int[] arr2) {
    int n = arr1.length;
    int i = 0;
    flag:
    for (int target : arr2) {
      while (arr1[i] == target) {
        if (++i >= n) {
          break flag;
        }
      }
      for (int j = i + 1; j < n; j++) {
        if (arr1[j] == target) {
          arraySwap(arr1, i, j);
          while (arr1[i] == target) {
            i++;
          }
        }
      }
    }
    Arrays.sort(arr1, i, n);
    return arr1;
  }

  private void arraySwap(int[] arr, int i, int j) {
    arr[i] = (arr[i] << 0xa) | arr[j];
    arr[j] = arr[i] >> 0xa;
    arr[i] &= 0x3ff;
  }

  public int[] relativeSortArray(int[] arr1, int[] arr2) {
    int[] bucket = new int[1001];
    for (int n : arr1) {
      bucket[n]++;
    }
    int i = 0;
    for (int target : arr2) {
      for (int k = 0; k < bucket[target]; k++) {
        arr1[i++] = target;
      }
      bucket[target] = 0;
    }
    for (int j = 0; j < 1001; j++) {
      if (bucket[j] <= 0) {
        continue;
      }
      for (int k = 0; k < bucket[j]; k++) {
        arr1[i++] = j;
      }
    }
    return arr1;
  }

  // 1154. 一年中的第几天
  public int dayOfYear(String date) {
    int year = Integer.parseInt(date.substring(0, 4));
    int month = Integer.parseInt(date.substring(5, 7));
    int day = Integer.parseInt(date.substring(8, 10));
    int days = 0;
    for (int i = 0; i < month - 1; i++) {
      days += MONTHS[i];
    }
    days += day;
    if (month > 2 && isLeap(year)) {
      days++;
    }
    return days;
  }

  private boolean isLeap(int year) {
    if (year % 100 == 0) {
      year /= 100;
    }
    return year % 4 == 0;
  }

  // 1365. 有多少小于当前数字的数字
  public int[] smallerNumbersThanCurrent(int[] nums) {
    int[] bucket = new int[101];
    for (int n : nums) {
      bucket[n]++;
    }
    int n = nums.length, c;
    int[] res = new int[n];
    for (int i = 0; i < n; i++) {
      c = 0;
      for (int j = nums[i] - 1; j >= 0; j--) {
        c += bucket[j];
      }
      res[i] = c;
    }
    return res;
  }

  // 1071. 字符串的最大公因子
  public String gcdOfStrings(String str1, String str2) {
    if (!(str1 + str2).equals(str2 + str1)) {
      return "";
    }
    if ("".equals(str1)) {
      return str2;
    }
    if ("".equals(str2)) {
      return str1;
    }
    if (str1.length() > str2.length()) {
      return gcdOfStrings(str1.replace(str2, ""), str2);
    }
    return gcdOfStrings(str2.replace(str1, ""), str1);
  }

  // 1037. 有效的回旋镖
  public boolean isBoomerang(int[][] points) {
    int x1 = points[0][0],
      y1 = points[0][1],
      x2 = points[1][0],
      y2 = points[1][1],
      x3 = points[2][0],
      y3 = points[2][1];
    boolean notSame = !(x1 == x2 && y1 == y2) && !(x2 == x3 && y2 == y3) && !(x3 == x1 && y3 == y1);
    boolean notSameLine1 = !(x1 == x2 && x2 == x3);
    double k1 = (double) (y1 - y2) / (x1 - x2);
    double k2 = (double) (y3 - y2) / (x3 - x2);
    return notSame && notSameLine1 && k1 != k2;
  }

  // 1013. 将数组分成和相等的三个部分
  public boolean canThreePartsEqualSum(int[] arr) {
    int n = arr.length;
    int[] sum = new int[n];
    sum[0] = arr[0];
    for (int i = 1; i < n; i++) {
      sum[i] = sum[i - 1] + arr[i];
    }
    int totalSum = sum[n - 1];
    if (totalSum % 3 != 0) {
      return false;
    }
    int every = totalSum / 3;
    int doubleEvery = every << 1;
    for (int i = 0; i < n; i++) {
      if (sum[i] == every) {
        for (int j = i + 1; j < n - 1; j++) {
          if (sum[j] == doubleEvery) {
            return true;
          }
        }
        return false;
      }
    }
    return false;
  }

  // 693. 交替位二进制数
  public boolean hasAlternatingBits(int n) {
    int x = n ^ (n >> 1);
    return (x & (x + 1)) == 0;
  }

  // 1047. 删除字符串中的所有相邻重复项
  public String removeDuplicates(String s) {
    StringBuilder builder = new StringBuilder();
    int n = s.length(), top = -1;
    char c;
    for (int i = 0; i < n; i++) {
      c = s.charAt(i);
      if (top >= 0 && builder.charAt(top) == c) {
        builder.deleteCharAt(top--);
      } else {
        builder.append(c);
        top++;
      }
    }
    return builder.toString();
  }

  // 941. 有效的山脉数组
  public boolean validMountainArray(int[] arr) {
    int n = arr.length;
    if (n < 3) {
      return false;
    }
    int i = 1;
    for (; i < n; i++) {
      if (arr[i] == arr[i - 1]) {
        return false;
      }
      if (arr[i] < arr[i - 1]) {
        break;
      }
    }
    int count = 1;
    for (; i < n; i++) {
      if (arr[i] >= arr[i - 1]) {
        return false;
      }
      count++;
    }
    return count > 1 && count < n;
  }

  // 1051. 高度检查器
  public int heightChecker1(int[] heights) {
    int n = heights.length;
    int[] expected = Arrays.copyOf(heights, n);
    Arrays.sort(expected);
    int res = 0;
    for (int i = 0; i < n; i++) {
      if (heights[i] != expected[i]) {
        res++;
      }
    }
    return res;
  }

  public int heightChecker(int[] heights) {
    int[] arr = new int[101];
    for (int i : heights) {
      arr[i]++;
    }
    int res = 0;
    for (int i = 1, j = 0; i < 101; i++) {
      while (arr[i]-- > 0) {
        if (heights[j++] != i) {
          res++;
        }
      }
    }
    return res;
  }

  // 953. 验证外星语词典
  public boolean isAlienSorted(String[] words, String order) {
    int[] dictOrder = new int[26];
    for (int i = 0; i < 26; i++) {
      dictOrder[order.charAt(i) - 'a'] = i;
    }
    int n = words.length;
    for (int i = 1; i < n; i++) {
      if (!isSorted(words[i - 1], words[i], dictOrder)) {
        return false;
      }
    }
    return true;
  }

  private boolean isSorted(String s1, String s2, int[] dictOrder) {
    int len1 = s1.length();
    int len2 = s2.length();
    int i = 0, j = 0;
    while (i < len1 && j < len2) {
      int diff = dictOrder[s1.charAt(i) - 'a'] - dictOrder[s2.charAt(j) - 'a'];
      if (diff < 0) {
        return true;
      } else if (diff > 0) {
        return false;
      }
      i++;
      j++;
    }
    return i >= len1;
  }

  //  2395. 和相等的子数组
  public boolean findSubarrays(int[] nums) {
    int n = nums.length;
    Set<Integer> set = new HashSet<>();
    for (int i = 1; i < n; i++) {
      if (!set.add(nums[i] + nums[i - 1])) {
        return true;
      }
    }
    return false;
  }

  // 1002. 查找共用字符
  public List<String> commonChars(String[] words) {
    int n = words.length;
    int[][] arr = new int[26][n];
    String word;
    int len;
    for (int i = 0; i < n; i++) {
      word = words[i];
      len = word.length();
      for (int j = 0; j < len; j++) {
        arr[word.charAt(j) - 'a'][i]++;
      }
    }
    List<String> list = new ArrayList<>();
    int min;
    for (int i = 0; i < 26; i++) {
      min = arr[i][0];
      for (int j = 1; j < n; j++) {
        min = Math.min(min, arr[i][j]);
      }
      for (int j = 0; j < min; j++) {
        list.add("" + (char) (i + 'a'));
      }
    }
    return list;
  }

  // 989. 数组形式的整数加法
  public List<Integer> addToArrayForm(int[] num, int k) {
    int n = num.length;
    List<Integer> list = new LinkedList<>();
    int over = 0, add;
    int i = n - 1;
    for (; i >= 0 || k > 0; i--) {
      add = (k % 10) + (i >= 0 ? num[i] : 0) + over;
      list.add(0, add % 10);
      over = add / 10;
      k /= 10;
    }
    if (over > 0) {
      list.add(0, over);
    }
    return list;
  }

  // 836. 矩形重叠
  public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
    // 水平方向不重合
    // rec1[2] <= rec2[0] || rec2[2] <= rec1[0]
    // 垂直方向不重合
    // rec1[3] <= rec2[1] || rec2[3] <= rec1[1]
    // 水平方向重合且垂直方向也重合
    // return !(rec1[2] <= rec2[0] || rec2[2] <= rec1[0]) && !(rec1[3] <= rec2[1] || rec2[3] <= rec1[1]);
    return !(rec1[2] <= rec2[0] || rec2[2] <= rec1[0] || rec1[3] <= rec2[1] || rec2[3] <= rec1[1]);
  }

  // 914. 卡牌分组
  public boolean hasGroupsSizeX(int[] deck) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int d : deck) {
      map.put(d, map.getOrDefault(d, 0) + 1);
    }
    Set<Integer> values = new HashSet<>(map.values());
    int g = -1;
    for (Integer v : values) {
      if (g < 0) {
        g = v;
      } else if ((g = gcd(g, v)) < 2) {
        return false;
      }
    }
    return g > 1;
  }

  private int gcd(int min, int max) {
    return min == 0 ? max : gcd(max % min, min);
  }

  // 892. 三维形体的表面积
  public int surfaceArea(int[][] grid) {
    int n = grid.length;
    int area = 0, curr;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (grid[i][j] == 0) {
          continue;
        }
        curr = (grid[i][j] << 2) + 2;
        if (i > 0) {
          curr -= Math.min(grid[i - 1][j], grid[i][j]);
        }
        if (j > 0) {
          curr -= Math.min(grid[i][j - 1], grid[i][j]);
        }
        if (i < n - 1) {
          curr -= Math.min(grid[i + 1][j], grid[i][j]);
        }
        if (j < n - 1) {
          curr -= Math.min(grid[i][j + 1], grid[i][j]);
        }
        area += curr;
      }
    }
    return area;
  }

  // 917. 仅仅反转字母
  public String reverseOnlyLetters(String s) {
    char[] chars = s.toCharArray();
    int i = 0, j = chars.length - 1;
    int x;
    while (i < j) {
      if (!Character.isAlphabetic(chars[i])) {
        i++;
      } else if (!Character.isAlphabetic(chars[j])) {
        j--;
      } else {
        x = chars[i] << 8 | chars[j];
        chars[i++] = (char) (x & 0xff);
        chars[j--] = (char) (x >> 8);
      }
    }
    return new String(chars);
  }

  // 922. 按奇偶排序数组 II
  public int[] sortArrayByParityII(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    int evenIndex = 0, oddIndex = 1;
    for (int num : nums) {
      if ((num & 1) == 0) {
        result[evenIndex] = num;
        evenIndex += 2;
      } else {
        result[oddIndex] = num;
        oddIndex += 2;
      }
    }
    return result;
  }

  // 929. 独特的电子邮件地址
  public int numUniqueEmails(String[] emails) {
    Set<String> set = new HashSet<>();
    String[] split;
    for (String email : emails) {
      split = email.split("@");
      set.add(doFilterLocalName(split[0]) + "@" + split[1]);
    }
    return set.size();
  }

  private String doFilterLocalName(String localName) {
    StringBuilder builder = new StringBuilder();
    int length = localName.length();
    char c;
    for (int i = 0; i < length; i++) {
      c = localName.charAt(i);
      if (c == '+') {
        break;
      }
      if (c == '.') {
        continue;
      }
      builder.append(c);
    }
    return builder.toString();
  }

  // 674. 最长连续递增序列
  public int findLengthOfLCIS(int[] nums) {
    int n = nums.length;
    int d = 1, max = 1;
    for (int i = 1; i < n; i++) {
      if (nums[i] > nums[i - 1]) {
        d++;
      } else {
        max = Math.max(max, d);
        d = 1;
      }
    }
    return Math.max(max, d);
  }

  // 661. 图片平滑器
  public int[][] imageSmoother(int[][] img) {
    int m = img.length;
    int n = img[0].length;
    int[][] result = new int[m][n];
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        result[i][j] = calImageSmoother(img, i, j, m, n);
      }
    }
    return result;
  }

  private int calImageSmoother(int[][] img, int i, int j, int m, int n) {
    int sum = img[i][j], count = 1;
    boolean hasUp = i > 0, hasDown = i < m - 1, hasLeft = j > 0, hasRight = j < n - 1;
    if (hasUp) {
      sum += img[i - 1][j];
      count++;
      if (hasLeft) {
        sum += img[i - 1][j - 1];
        count++;
      }
      if (hasRight) {
        sum += img[i - 1][j + 1];
        count++;
      }
    }
    if (hasDown) {
      sum += img[i + 1][j];
      count++;
      if (hasLeft) {
        sum += img[i + 1][j - 1];
        count++;
      }
      if (hasRight) {
        sum += img[i + 1][j + 1];
        count++;
      }
    }
    if (hasLeft) {
      sum += img[i][j - 1];
      count++;
    }
    if (hasRight) {
      sum += img[i][j + 1];
      count++;
    }
    return sum / count;
  }

  // 657. 机器人能否返回原点
  public boolean judgeCircle(String moves) {
    int[] arr = new int[26];
    int n = moves.length();
    for (int i = 0; i < n; i++) {
      arr[moves.charAt(i) - 'A']++;
    }
    return arr['U' - 'A'] == arr['D' - 'A'] && arr['L' - 'A'] == arr['R' - 'A'];
  }

  // 643. 子数组最大平均数 I
  public double findMaxAverage1(int[] nums, int k) {
    int n = nums.length;
    int[] sum = new int[n];
    sum[0] = nums[0];
    for (int i = 1; i < n; i++) {
      sum[i] = sum[i - 1] + nums[i];
    }
    int max = sum[k - 1];
    for (int i = k; i < n; i++) {
      int diff = sum[i] - sum[i - k];
      if (diff > max) {
        max = diff;
      }
    }
    return (double) max / k;
  }

  public double findMaxAverage(int[] nums, int k) {
    int n = nums.length;
    int init = 0;
    for (int i = 0; i < k; i++) {
      init += nums[i];
    }
    int max = init;
    for (int i = k; i < n; i++) {
      init += nums[i] - nums[i - k];
      max = Math.max(max, init);
    }
    return (double) max / k;
  }

  // 628. 三个数的最大乘积
  public int maximumProduct1(int[] nums) {
    int n = nums.length;
    Arrays.sort(nums);
    return Math.max(nums[0] * nums[1] * nums[n - 1], nums[n - 1] * nums[n - 2] * nums[n - 3]);
  }

  public int maximumProduct(int[] nums) {
    int max1 = -1001, max2 = -1001, max3 = -1001, min1 = 1001, min2 = 1001;
    for (int num : nums) {
      if (num > max1) {
        max3 = max2;
        max2 = max1;
        max1 = num;
      } else if (num > max2) {
        max3 = max2;
        max2 = num;
      } else if (num > max3) {
        max3 = num;
      }
      if (num < min1) {
        min2 = min1;
        min1 = num;
      } else if (num < min2) {
        min2 = num;
      }
    }
    return Math.max(max1 * max2 * max3, max1 * min1 * min2);
  }

  // 884. 两句话中的不常见单词
  public String[] uncommonFromSentences(String s1, String s2) {
    Map<String, Integer> map = new HashMap<>();
    String[] split = s1.split(" ");
    for (String s : split) {
      map.put(s, map.getOrDefault(s, 0) + 1);
    }
    split = s2.split(" ");
    for (String s : split) {
      map.put(s, map.getOrDefault(s, 0) + 1);
    }
    List<String> list = new ArrayList<>();
    for (Map.Entry<String, Integer> e : map.entrySet()) {
      if (e.getValue() == 1) {
        list.add(e.getKey());
      }
    }
    return list.toArray(new String[0]);
  }

  // 733. 图像渲染
  public int[][] floodFill(int[][] image, int sr, int sc, int color) {
    if (image[sr][sc] == color) {
      return image;
    }
    int rows = image.length;
    int cols = image[0].length;
    int[][] bak = new int[rows][cols];
    doFill(rows, cols, image, sr, sc, color, bak);
    return image;
  }

  private void doFill(int rows, int cols, int[][] image, int sr, int sc, int color, int[][] bak) {
    bak[sr][sc] = image[sr][sc];
    image[sr][sc] = color;
    if (sr > 0 && image[sr - 1][sc] == bak[sr][sc]) {
      doFill(rows, cols, image, sr - 1, sc, color, bak);
    }
    if (sc > 0 && image[sr][sc - 1] == bak[sr][sc]) {
      doFill(rows, cols, image, sr, sc - 1, color, bak);
    }
    if (sr < rows - 1 && image[sr + 1][sc] == bak[sr][sc]) {
      doFill(rows, cols, image, sr + 1, sc, color, bak);
    }
    if (sc < cols - 1 && image[sr][sc + 1] == bak[sr][sc]) {
      doFill(rows, cols, image, sr, sc + 1, color, bak);
    }
  }

  // 883. 三维形体投影面积
  public int projectionArea(int[][] grid) {
    int n = grid.length;
    int xOy = 0, zOx = 0, yOz = 0;
    for (int i = 0; i < n; i++) {
      int rowMax = 0, colMax = 0;
      for (int j = 0; j < n; j++) {
        if (grid[i][j] > 0) {
          xOy++;
        }
        if (grid[i][j] > rowMax) {
          rowMax = grid[i][j];
        }
        if (grid[j][i] > colMax) {
          colMax = grid[j][i];
        }
      }
      zOx += rowMax;
      yOz += colMax;
    }
    return xOy + yOz + zOx;
  }

  // 832. 翻转图像
  public int[][] flipAndInvertImage1(int[][] image) {
    int n = image.length, end = n >> 1;
    boolean flag = (n & 1) == 1;
    for (int[] row : image) {
      for (int i = 0; i < end; i++) {
        row[i] = (row[i] << 1) | row[n - i - 1];
        row[n - i - 1] = (row[i] >> 1) ^ 1;
        row[i] = (row[i] & 1) ^ 1;
      }
      if (flag) {
        row[end] ^= 1;
      }
    }
    return image;
  }

  public int[][] flipAndInvertImage(int[][] image) {
    int n = image.length, end = n >> 1, right;
    boolean flag = (n & 1) == 1;
    for (int[] row : image) {
      for (int left = 0; left < end; left++) {
        right = n - left - 1;
        if (row[left] == row[right]) {
          row[left] ^= 1;
          row[right] ^= 1;
        }
      }
      if (flag) {
        row[end] ^= 1;
      }
    }
    return image;
  }

  // 860. 柠檬水找零
  public boolean lemonadeChange(int[] bills) {
    int dollar5 = 0, dollar10 = 0;
    for (int bill : bills) {
      switch (bill) {
        case 5:
          dollar5++;
          break;
        case 10:
          if (--dollar5 < 0) {
            return false;
          }
          dollar10++;
          break;
        case 20:
          if (dollar5 > 0 && dollar10 > 0) {
            dollar5--;
            dollar10--;
          } else if (dollar5 > 2) {
            dollar5 -= 3;
          } else {
            return false;
          }
          break;
        default:
          break;
      }
    }
    return true;
  }

  // 2389. 和有限的最长子序列
  public int[] answerQueries(int[] nums, int[] queries) {
    Arrays.sort(nums);
    int n = nums.length;
    for (int i = 1; i < n; i++) {
      nums[i] = nums[i - 1] + nums[i];
    }
    int m = queries.length;
    int[] answer = new int[m];
    for (int i = 0; i < m; i++) {
      answer[i] = findAnswerQueries(nums, queries[i]) + 1;
    }
    return answer;
  }

  private int findAnswerQueries(int[] arr, int target) {
    int left = 0, right = arr.length - 1, mid;
    if (left == right) {
      return arr[0] > target ? -1 : 0;
    }
    while (left < right) {
      if (arr[left] > target) {
        return left - 1;
      }
      if (arr[left] == target) {
        return left;
      }
      if (arr[right] <= target) {
        return right;
      }
      mid = left + ((right - left) >> 1);
      if (mid == left || mid == right) {
        break;
      }
      if (arr[mid] > target) {
        right = mid;
      } else {
        left = mid;
      }
    }
    return left;
  }

  // 594. 最长和谐子序列
  public int findLHS1(int[] nums) {
    int longest = 0;
    int len = nums.length, l, r, curr1, curr2;
    boolean flag1, flag2;
    for (int i = 0; i < len && i <= (len - longest); i++) {
      l = nums[i] - 1;
      r = nums[i] + 1;
      curr1 = 1;
      curr2 = 1;
      flag1 = false;
      flag2 = false;
      for (int j = i + 1; j < len; j++) {
        if (nums[j] == nums[i]) {
          curr1++;
          curr2++;
        }
        if (nums[j] == l) {
          curr1++;
          flag1 = true;
        }
        if (nums[j] == r) {
          curr2++;
          flag2 = true;
        }
      }
      if (flag1 && curr1 > longest) {
        longest = curr1;
      }
      if (flag2 && curr2 > longest) {
        longest = curr2;
      }
    }
    return longest;
  }

  public int findLHS(int[] nums) {
    Map<Integer, Integer> map = new TreeMap<>();
    for (int num : nums) {
      map.put(num, map.getOrDefault(num, 0) + 1);
    }
    int i = 0, pre = -2, longest = 0;
    for (Map.Entry<Integer, Integer> e : map.entrySet()) {
      if (i++ == 0) {
        pre = e.getKey();
      } else {
        if (Math.abs(e.getKey() - pre) == 1) {
          longest = Math.max(longest, e.getValue() + map.get(pre));
        }
        pre = e.getKey();
      }
    }
    return longest;
  }

  // 2383. 赢得比赛需要的最少训练时长
  public int minNumberOfHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) {
    int len = energy.length;
    int sum = 0, diff1, diff2;
    for (int i = 0; i < len; i++) {
      diff1 = Math.max(energy[i] + 1 - initialEnergy, 0);
      diff2 = Math.max(experience[i] + 1 - initialExperience, 0);
      sum += diff1 + diff2;
      initialEnergy = initialEnergy + diff1 - energy[i];
      initialExperience += diff2 + experience[i];
    }
    return sum;
  }

  // 2379. 得到 K 个黑块的最少涂色次数
  public int minimumRecolors(String blocks, int k) {
    int len = blocks.length(), whiteCount = 0;
    for (int i = 0; i < k; i++) {
      if (blocks.charAt(i) == 'W') {
        whiteCount++;
      }
    }
    int min = whiteCount;
    for (int i = k; i < len; i++) {
      if (blocks.charAt(i) == 'W') {
        whiteCount++;
      }
      if (blocks.charAt(i - k) == 'W') {
        whiteCount--;
      }
      if (whiteCount < min) {
        min = whiteCount;
      }
    }
    return min;
  }

  // 1103. 分糖果 II
  public int[] distributeCandies(int candies, int num_people) {
    int n = (int) (Math.sqrt(((long) candies << 1) + 0.25) - 0.5);
    int a = n / num_people, b = n % num_people;
    int[] people = new int[num_people];
    for (int i = 0; i < b; i++) {
      people[i] = (i + 1 + i + 1 + (a) * num_people) * (a + 1) / 2;
    }
    for (int i = b; i < num_people; i++) {
      people[i] = (i + 1 + i + 1 + (a - 1) * num_people) * a / 2;
    }
    people[b] += (candies - n * (n + 1) / 2);
    return people;
  }

  // 925. 长按键入
  public boolean isLongPressedName(String name, String typed) {
    if (name.charAt(0) != typed.charAt(0)) {
      return false;
    }
    int len1 = name.length();
    int len2 = typed.length();
    int j = 0;
    char expected, curr, pre = 0;
    for (int i = 0; i < len1; i++) {
      expected = name.charAt(i);
      while (j < len2 && (curr = typed.charAt(j)) != expected) {
        if (curr != pre) {
          return false;
        }
        j++;
      }
      if (j >= len2) {
        return false;
      }
      j++;
      pre = expected;
    }
    while (j < len2) {
      if (typed.charAt(j++) != pre) {
        return false;
      }
    }
    return true;
  }

  //  908. 最小差值 I
  public int smallestRangeI(int[] nums, int k) {
    int min = (int) 1e4 + 1, max = -1;
    for (int num : nums) {
      if (num > max) {
        max = num;
      }
      if (num < min) {
        min = num;
      }
    }
    return Math.max(max - min - (k << 1), 0);
  }

  // 888. 公平的糖果交换
  public int[] fairCandySwap(int[] aliceSizes, int[] bobSizes) {
    int diff = (Arrays.stream(aliceSizes).sum() - Arrays.stream(bobSizes).sum()) >> 1;
    Set<Integer> set = new HashSet<>(bobSizes.length);
    for (int b : bobSizes) {
      set.add(b);
    }
    int y;
    for (int x : aliceSizes) {
      if (set.contains(y = x - diff)) {
        return new int[]{x, y};
      }
    }
    return null;
  }

  // 844. 比较含退格的字符串
  public boolean backspaceCompare1(String s, String t) {
    Stack<Character> stack1 = new Stack<>();
    Stack<Character> stack2 = new Stack<>();
    int len1 = s.length();
    int len2 = t.length();
    char c;
    for (int i = 0; i < len1; i++) {
      if ((c = s.charAt(i)) == '#') {
        if (!stack1.empty()) {
          stack1.pop();
        }
      } else {
        stack1.push(c);
      }
    }
    for (int i = 0; i < len2; i++) {
      if ((c = t.charAt(i)) == '#') {
        if (!stack2.empty()) {
          stack2.pop();
        }
      } else {
        stack2.push(c);
      }
    }
    while (!stack1.empty() && !stack2.empty()) {
      if (!stack1.pop().equals(stack2.pop())) {
        return false;
      }
    }
    return stack1.empty() && stack2.empty();
  }

  public boolean backspaceCompare(String s, String t) {
    int i = s.length() - 1, j = t.length() - 1;
    int skip1 = 0, skip2 = 0;
    while (i >= 0 || j >= 0) {
      while (i >= 0) {
        if (s.charAt(i) == '#') {
          skip1++;
          i--;
          continue;
        } else if (skip1 > 0) {
          skip1--;
          i--;
          continue;
        }
        break;
      }
      while (j >= 0) {
        if (t.charAt(j) == '#') {
          skip2++;
          j--;
          continue;
        } else if (skip2 > 0) {
          skip2--;
          j--;
          continue;
        }
        break;
      }
      if (i == -1 && j == -1) {
        return true;
      }
      if (i == -1 || j == -1 || s.charAt(i--) != t.charAt(j--)) {
        return false;
      }
    }
    return true;
  }

  // 1089. 复写零
  public void duplicateZeros1(int[] arr) {
    int len = arr.length;
    int lastIndex = len - 1;
    for (int i = 0; i < len; ) {
      if (arr[i] == 0) {
        if (lastIndex - i >= 0) {
          System.arraycopy(arr, i, arr, i + 1, lastIndex - i);
        }
        i += 2;
      } else {
        i++;
      }
    }
  }

  public void duplicateZeros(int[] arr) {
    int len = arr.length;
    int count = 0, i = 0;
    boolean flag = false;
    while (count < len) {
      count++;
      if (arr[i++] == 0 && count < len) {
        if (++count >= len) {
          flag = true;
        }
      }
    }
    int start = --i;
    int fixed = len - 1;
    while (i >= 0 & fixed >= 0) {
      arr[fixed--] = arr[i];
      if (arr[i] == 0 && fixed >= 0 && (i < start || flag)) {
        arr[fixed--] = 0;
      }
      i--;
    }
  }

  // 1046. 最后一块石头的重量
  public int lastStoneWeight(int[] stones) {
    int len = stones.length;
    PriorityQueue<Integer> queue = new PriorityQueue<>(len, (o1, o2) -> -Integer.compare(o1, o2));
    for (int stone : stones) {
      queue.offer(stone);
    }
    int max, min;
    while (queue.size() > 1) {
      max = queue.poll();
      min = queue.poll();
      if (max > min) {
        queue.offer(max - min);
      }
    }
    return queue.isEmpty() ? 0 : queue.poll();
  }

  // 1018. 可被 5 整除的二进制前缀
  public List<Boolean> prefixesDivBy5(int[] nums) {
    int len = nums.length;
    List<Boolean> list = new ArrayList<>(len);
    long pre = 0;
    for (int num : nums) {
      pre = ((pre << 1) + num) % 5;
      list.add(pre % 5 == 0);
    }
    return list;
  }

  // 面试题 05.02. 二进制数转字符串
  public String printBin(double num) {
    StringBuilder builder = new StringBuilder("0.");
    for (int i = 0; i < 30; i++) {
      builder.append((int) (num *= 2) & 1);
      if (num == (int) num) {
        return builder.toString();
      }
    }
    return "ERROR";
  }

  public int[] playQq(int[] ori) {
    int len = ori.length;
    int[] arr = Arrays.copyOfRange(ori, 0, len << 1);
    int[] result = new int[len];
    int head = 0, tail = len, i = 0;
    while (head < tail) {
      result[i++] = arr[head];
      if (head < tail - 1) {
        arr[tail++] = arr[head + 1];
      }
      head += 2;
    }
    return result;
  }

  // 1078. Bigram 分词
  public String[] findOcurrences(String text, String first, String second) {
    String[] strings = text.split(" ");
    List<String> list = new ArrayList<>();
    int len = strings.length;
    for (int i = 0; i < len; i++) {
      if (strings[i].equals(first)) {
        if (i < len - 1 && strings[i + 1].equals(second)) {
          if (i < len - 2) {
            list.add(strings[i + 2]);
          }
        }
      }
    }
    return list.toArray(new String[0]);
  }

  // 2373. 矩阵中的局部最大值
  public int[][] largestLocal(int[][] grid) {
    int srcLen = grid.length;
    int destLen = srcLen - 2;
    int[][] result = new int[destLen][destLen];
    for (int i = 2; i < srcLen; i++) {
      for (int j = 2; j < srcLen; j++) {
        result[i - 2][j - 2] = largestValue(grid, i, j);
      }
    }
    return result;
  }

  private int largestValue(int[][] grid, int maxRow, int maxCol) {
    int max = 0;
    for (int i = maxRow - 2; i <= maxRow; i++) {
      for (int j = maxCol - 2; j <= maxCol; j++) {
        if (grid[i][j] > max) {
          max = grid[i][j];
        }
      }
    }
    return max;
  }

  // 868. 二进制间距
  public int binaryGap(int n) {
    int pre = 0, i = 1, max = 0, diff;
    while (n != 0) {
      if ((n & 1) == 1) {
        diff = i - pre;
        if (pre != 0 && diff > max) {
          max = diff;
        }
        pre = i;
      }
      i++;
      n >>= 1;
    }
    return max;
  }

  // 896. 单调数列
  public boolean isMonotonic1(int[] nums) {
    int len = nums.length;
    if (len < 3) {
      return true;
    }
    int flag = 0;
    for (int i = 1; i < len; i++) {
      if (nums[i] > nums[i - 1]) {
        if (flag == -1) {
          return false;
        }
        flag = 1;
      } else if (nums[i] < nums[i - 1]) {
        if (flag == 1) {
          return false;
        }
        flag = -1;
      }
    }
    return true;
  }

  public boolean isMonotonic(int[] nums) {
    int len = nums.length;
    if (len < 3) {
      return true;
    }
    boolean inc = false;
    boolean dec = false;
    for (int i = 1; i < len; i++) {
      if (nums[i] > nums[i - 1]) {
        if (dec) {
          return false;
        }
        inc = true;
      } else if (nums[i] < nums[i - 1]) {
        if (inc) {
          return false;
        }
        dec = true;
      }
    }
    return true;
  }

  // 867. 转置矩阵
  public int[][] transpose(int[][] matrix) {
    int m = matrix.length;
    int n = matrix[0].length;
    int[][] result = new int[n][m];
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        result[j][i] = matrix[i][j];
      }
    }
    return result;
  }

  // 830. 较大分组的位置
  public List<List<Integer>> largeGroupPositions(String s) {
    List<List<Integer>> list = new ArrayList<>();
    int len = s.length();
    if (len < 3) {
      return list;
    }
    int start = 0;
    for (int i = 1; i < len; i++) {
      if (s.charAt(i) != s.charAt(start)) {
        if (i - start >= 3) {
          list.add(Arrays.asList(start, i - 1));
        }
        start = i;
      }
    }
    if (len - start >= 3) {
      list.add(Arrays.asList(start, len - 1));
    }
    return list;
  }

  // 2363. 合并相似的物品
  public List<List<Integer>> mergeSimilarItems1(int[][] items1, int[][] items2) {
    List<List<Integer>> list = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();
    int len = items1.length;
    for (int i = 0; i < len; i++) {
      map.put(items1[i][0], items1[i][1]);
    }
    len = items2.length;
    for (int i = 0; i < len; i++) {
      map.put(items2[i][0], map.getOrDefault(items2[i][0], 0) + items2[i][1]);
    }
    for (Map.Entry<Integer, Integer> e : map.entrySet()) {
      list.add(Arrays.asList(e.getKey(), e.getValue()));
    }
    list.sort(Comparator.comparingInt(o -> o.get(0)));
    return list;
  }

  public List<List<Integer>> mergeSimilarItems(int[][] items1, int[][] items2) {
    Comparator<int[]> c = Comparator.comparingInt(o -> o[0]);
    Arrays.sort(items1, c);
    Arrays.sort(items2, c);
    List<List<Integer>> list = new ArrayList<>();
    int len1 = items1.length;
    int len2 = items2.length;
    int i = 0, j = 0;
    while (i < len1 && j < len2) {
      if (items1[i][0] == items2[j][0]) {
        list.add(Arrays.asList(items1[i][0], items1[i][1] + items2[j][1]));
        i++;
        j++;
      } else if (items1[i][0] > items2[j][0]) {
        list.add(Arrays.asList(items2[j][0], items2[j][1]));
        j++;
      } else {
        list.add(Arrays.asList(items1[i][0], items1[i][1]));
        i++;
      }
    }
    while (i < len1) {
      list.add(Arrays.asList(items1[i][0], items1[i][1]));
      i++;
    }
    while (j < len2) {
      list.add(Arrays.asList(items2[j][0], items2[j][1]));
      j++;
    }
    return list;
  }

  // 819. 最常见的单词
  public String mostCommonWord(String paragraph, String[] banned) {
    Set<String> bannedWords = new HashSet<>(Arrays.asList(banned));
    Map<String, Integer> map = new HashMap<>();
    int start = -1, max = -1;
    String s;
    int len = paragraph.length();
    for (int i = 0; i < len; i++) {
      if (!Character.isAlphabetic(paragraph.charAt(i))) {
        if (start != -1) {
          s = paragraph.substring(start, i).toLowerCase();
          start = -1;
          if (!bannedWords.contains(s)) {
            max = Math.max(max, collectToMap(s, map));
          }
        }
      } else {
        if (start == -1) {
          start = i;
        } else if (i == len - 1) {
          s = paragraph.substring(start).toLowerCase();
          if (!bannedWords.contains(s)) {
            max = Math.max(max, collectToMap(s, map));
          }
        }
      }
    }
    for (Map.Entry<String, Integer> e : map.entrySet()) {
      if (e.getValue() == max) {
        return e.getKey();
      }
    }
    return null;
  }

  private int collectToMap(String s, Map<String, Integer> map) {
    int count = map.getOrDefault(s, 0) + 1;
    map.put(s, count);
    return count;
  }

  // 859. 亲密字符串
  public boolean buddyStrings(String s, String goal) {
    int len = s.length();
    if (goal.length() != len) {
      return false;
    }
    int[] count = new int[26];
    boolean doubleSame = false;
    int index1 = -1, index2 = -1;
    char c;
    for (int i = 0; i < len; i++) {
      c = s.charAt(i);
      if (c != goal.charAt(i)) {
        if (index1 == -1) {
          index1 = i;
        } else if (index2 == -1) {
          index2 = i;
        } else {
          return false;
        }
      }
      if (count[c - 'a']++ > 0) {
        doubleSame = true;
      }
    }
    if (index1 == -1 && index2 == -1) {
      return doubleSame;
    }
    return index2 != -1 && s.charAt(index1) == goal.charAt(index2) && s.charAt(index2) == goal.charAt(index1);
  }

  // 821. 字符的最短距离
  public int[] shortestToChar1(String s, char c) {
    int len = s.length();
    int[] result = new int[len];
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < len; i++) {
      if (s.charAt(i) == c) {
        list.add(i);
      }
    }
    int size = list.size();
    for (int i = 0; i < size; i++) {
      int curr = list.get(i);
      if (i == 0) {
        for (int j = 0; j < curr; j++) {
          result[j] = curr - j;
        }
      }
      if (i == size - 1) {
        for (int j = curr; j < len; j++) {
          result[j] = j - curr;
        }
        break;
      }
      int next = list.get(i + 1);
      /*
       * 计算"中间位置"的下标：(2+6)/2=4，(6+11)/2=8
       * 因此均按照 “mid及其之前的靠左、mid之后的靠右” 的原则处理即可
       * 为避免重复操作，统一采取 “左开右闭” 的区间
       * */
      int mid = (list.get(i) + next) >> 1;
      for (int j = curr; j <= mid; j++) {
        result[j] = j - curr;
      }
      for (int j = mid + 1; j < next; j++) {
        result[j] = next - j;
      }
    }
    return result;
  }

  public int[] shortestToChar(String s, char c) {
    int len = s.length();
    int[] result = new int[len];
    int index = -2 * len;
    for (int i = 0; i < len; i++) {
      if (s.charAt(i) == c) {
        index = i;
      }
      result[i] = i - index;
    }
    for (int i = index - 1; i >= 0; i--) {
      if (s.charAt(i) == c) {
        index = i;
      }
      result[i] = Math.min(result[i], index - i);
    }
    return result;
  }

  // 2357. 使数组中所有元素都等于零
  public int minimumOperations1(int[] nums) {
    Arrays.sort(nums);
    int len = nums.length;
    int sum = 0;
    for (int i = 0; i < len; i++) {
      if (nums[i] != 0) {
        for (int j = i + 1; j < len; j++) {
          nums[j] -= nums[i];
        }
        // nums[i] = 0;
        sum++;
      }
    }
    return sum;
  }

  public int minimumOperations(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) {
      if (n > 0) {
        set.add(n);
      }
    }
    return set.size();
  }

  // 796. 旋转字符串
  public boolean rotateString(String s, String goal) {
    // return s.length() == goal.length() && (s + s).contains(goal);
    char[] chars1 = s.toCharArray();
    char[] chars2 = goal.toCharArray();
    int len1 = chars1.length, len2 = chars2.length;
    if (len1 != len2) {
      return false;
    }
    Queue<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < len1; i++) {
      if (chars1[i] == chars2[0]) {
        queue.offer(i);
      }
    }
    if (queue.isEmpty()) {
      return false;
    }
    int j = -1;
    while (!queue.isEmpty()) {
      j = 0;
      for (int i = queue.poll(); j < len2; i = (i + 1) % len1, j++) {
        if (chars1[i] != chars2[j]) {
          break;
        }
      }
      if (j == len2) {
        return true;
      }
    }
    return false;
  }

  // 804. 唯一摩尔斯密码词
  public int uniqueMorseRepresentations1(String[] words) {
    Set<String> set = new HashSet<>();
    for (String word : words) {
      StringBuilder builder = new StringBuilder();
      for (int i = 0; i < word.length(); i++) {
        builder.append(MORSE_DICT[word.charAt(i) - 'a']);
      }
      set.add(builder.toString());
    }
    return set.size();
  }

  public int uniqueMorseRepresentations(String[] words) {
    // for (String s : MORSE_DICT) {
    //   System.out.printf("new int[]{0x%s, %d},%n", Integer.toHexString(Integer.parseInt(toS(s), 2)), s.length());
    // }
    Set<Integer> set = new HashSet<>();
    int x, len, charAt;
    for (String word : words) {
      x = 0;
      len = word.length();
      for (int i = 0; i < len; i++) {
        charAt = word.charAt(i) - 'a';
        x = ((x << MORSE_DICT_PLUS[charAt][1]) | MORSE_DICT_PLUS[charAt][0]);
      }
      set.add(x);
    }
    return set.size();
  }

  private String toS(String s) {
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
      builder.append(s.charAt(i) == '-' ? 1 : 0);
    }
    return builder.toString();
  }

  // 766. 托普利茨矩阵
  public boolean isToeplitzMatrix1(int[][] matrix) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int max = Math.max(rows, cols);
    for (int diff = 0; diff <= max; diff++) {
      int sameUp = -1, sameDown = -1, j;
      for (int i = 0; i < rows; i++) {
        j = i + diff;
        if (j < cols) {
          if (sameUp == -1) {
            sameUp = matrix[i][j];
          } else if (matrix[i][j] != sameUp) {
            return false;
          }
        }
        if (j < rows && i < cols) {
          if (sameDown == -1) {
            sameDown = matrix[j][i];
          } else if (matrix[j][i] != sameDown) {
            return false;
          }
        }
      }
    }
    return true;
  }

  public boolean isToeplitzMatrix(int[][] matrix) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    for (int i = 1; i < rows; i++) {
      for (int j = 1; j < cols; j++) {
        if (matrix[i][j] != matrix[i - 1][j - 1]) {
          return false;
        }
      }
    }
    return true;
  }

  // 762. 二进制表示中质数个计算置位
  public int countPrimeSetBits1(int left, int right) {
    Set<Integer> primeNumbers = new HashSet<>();
    int sum = 0, count;
    for (int i = left; i <= right; i++) {
      count = Integer.bitCount(i);
      if (primeNumbers.contains(count)) {
        sum++;
      } else if (isPrime(count)) {
        sum++;
        primeNumbers.add(count);
      }
    }
    return sum;
  }

  private boolean isPrime(int n) {
    if (n < 2) {
      return false;
    }
    for (int i = 2; i <= ((int) Math.sqrt(n)); i++) {
      if (n % i == 0) {
        return false;
      }
    }
    return true;
  }

  public int countPrimeSetBits(int left, int right) {
    // right <= 1e10 < Math.pow(2, 20)
    // any < Math.pow(2, 20) - 1 = 0111 1111 1111 1111 1111
    // 即1的个数最多有19个。不超过19的质数是可穷举的：2、3、5、7、11、13、17和19
    // 因此只需要存储这几个数字即可：1010 0010 1000 1010 1100
    // 即 0xa28ac. 判断一个数n是不是质数，只要将1左移n位，再与 0xa28ac 按位相与，如果不是质数则结果为0，否则非0
    int sum = 0;
    for (int i = left; i <= right; i++) {
      if (((1 << Integer.bitCount(i)) & 0xa28ac) == 0) {
        continue;
      }
      sum++;
    }
    return sum;
  }

  // 748. 最短补全词
  public String shortestCompletingWord(String licensePlate, String[] words) {
    char[] target = new char[26];
    int len = licensePlate.length();
    char c;
    for (int i = 0; i < len; i++) {
      c = licensePlate.charAt(i);
      if (c >= 'a' && c <= 'z') {
        target[c - 'a']++;
      } else if (c >= 'A' && c <= 'Z') {
        target[(c | 0x20) - 'a']++;
      }
    }
    int minLen = Integer.MAX_VALUE;
    String finalWord = null;
    for (String word : words) {
      len = word.length();
      if (matchShortestCompletingWord(word, target) && len < minLen) {
        finalWord = word;
        minLen = len;
      }
    }
    return finalWord;
  }

  private boolean matchShortestCompletingWord(String word, char[] target) {
    char[] chars = new char[26];
    int len = word.length();
    for (int i = 0; i < len; i++) {
      chars[word.charAt(i) - 'a']++;
    }
    for (int i = 0; i < 26; i++) {
      if (target[i] > 0 && chars[i] < target[i]) {
        return false;
      }
    }
    return true;
  }

  // 747. 至少是其他数字两倍的最大数
  public int dominantIndex1(int[] nums) {
    int len = nums.length, maxVal = -1, maxIndex = -1;
    for (int i = 0; i < len; i++) {
      if (nums[i] > maxVal) {
        maxVal = nums[i];
        maxIndex = i;
      }
    }
    maxVal >>= 1;
    for (int i = 0; i < len; i++) {
      if (i != maxIndex && nums[i] > maxVal) {
        return -1;
      }
    }
    return maxIndex;
  }

  public int dominantIndex(int[] nums) {
    int len = nums.length, maxVal, maxIndex = -1, firstMax = -1, secondMax = -1;
    for (int i = 0; i < len; i++) {
      if (nums[i] > firstMax) {
        secondMax = firstMax;
        firstMax = nums[i];
        maxIndex = i;
      } else if (nums[i] > secondMax) {
        secondMax = nums[i];
      }
    }
    return (firstMax >> 1) >= secondMax ? maxIndex : -1;
  }

  // 744. 寻找比目标字母大的最小字母
  public char nextGreatestLetter(char[] letters, char target) {
    for (char c : letters) {
      if (c > target) {
        return c;
      }
    }
    return letters[0];
  }

  // 724. 寻找数组的中心下标
  public int pivotIndex(int[] nums) {
    int sum = 0;
    for (int n : nums) {
      sum += n;
    }
    int left = 0;
    int len = nums.length;
    for (int i = 0; i < len; i++) {
      sum -= nums[i];
      if (left == sum) {
        return i;
      }
      left += nums[i];
    }
    return -1;
  }

  // 717. 1 比特与 2 比特字符
  public boolean isOneBitCharacter(int[] bits) {
    int len = bits.length;
    int i = 0;
    while (i < len) {
      if (bits[i] == 0) {
        if (++i == len) {
          return true;
        }
      } else {
        i += 2;
      }
    }
    return false;
  }

  // 728. 自除数
  public List<Integer> selfDividingNumbers(int left, int right) {
    List<Integer> result = new ArrayList<>();
    for (int i = left; i <= right; i++) {
      if (isSelfDividingNumber(i)) {
        result.add(i);
      }
    }
    return result;
  }

  private boolean isSelfDividingNumber(int n) {
    if (n < 10) {
      return true;
    }
    int x, k = n;
    while (k > 0) {
      x = k % 10;
      if (x == 0 || (n % x) != 0) {
        return false;
      }
      k /= 10;
    }
    return true;
  }

  // 605. 种花问题
  public boolean canPlaceFlowers1(int[] flowerbed, int n) {
    if (n == 0) {
      return true;
    }
    int len = flowerbed.length;
    if (len == 0) {
      return false;
    }
    if (len == 1) {
      return flowerbed[0] == 0 && n <= 1;
    }
    List<Integer> list = new ArrayList<>();
    int start = 0;
    for (int i = 1; i < len; i++) {
      if (flowerbed[i] != flowerbed[i - 1]) {
        list.add(i - start);
        start = i;
      }
      if (i == len - 1) {
        list.add(len - start);
      }
    }
    int size = list.size();
    if (size == 1) {
      return ((list.get(0) + 1) >> 1) >= n;
    }
    int endIndex = size - 1;
    for (int i = flowerbed[0]; i < size; i += 2) {
      if (i == 0 || i == endIndex) {
        n -= (list.get(i) >> 1);
      } else {
        n -= ((list.get(i) - 1) >> 1);
      }
      if (n <= 0) {
        return true;
      }
    }
    return false;
  }

  public boolean canPlaceFlowers(int[] flowerbed, int n) {
    if (n == 0) {
      return true;
    }
    int len = flowerbed.length;
    for (int i = 0; i < len; i++) {
      if (flowerbed[i] != 0) {
        continue;
      }
      if ((i == 0 || flowerbed[i - 1] == 0) && (i == len - 1 || flowerbed[i + 1] == 0)) {
        flowerbed[i] = 1;
        if (--n <= 0) {
          return true;
        }
      }
    }
    return false;
  }

  // 599. 两个列表的最小索引总和
  public String[] findRestaurant(String[] list1, String[] list2) {
    int len1 = list1.length;
    int len2 = list2.length;
    Map<String, Integer> map = new HashMap<>();
    for (int i = 0; i < len1; i++) {
      map.put(list1[i], i);
    }
    Set<String> result = new HashSet<>();
    int minIndexSum = Integer.MAX_VALUE;
    int currIndexSum;
    Integer alreadyIndex;
    for (int i = 0; i < len2; i++) {
      alreadyIndex = map.get(list2[i]);
      if (alreadyIndex == null) {
        continue;
      }
      currIndexSum = alreadyIndex + i;
      if (currIndexSum > minIndexSum) {
        break;
      }
      if (currIndexSum < minIndexSum) {
        minIndexSum = currIndexSum;
        result.clear();
      }
      result.add(list2[i]);
    }
    return result.toArray(new String[0]);
  }

  // 566. 重塑矩阵
  public int[][] matrixReshape1(int[][] mat, int r, int c) {
    int rows = mat.length;
    int cols = mat[0].length;
    if (r * c != rows * cols) {
      return mat;
    }
    int[][] result = new int[r][c];
    int k = 0;
    for (int ri = 0; ri < r; ri++) {
      for (int ci = 0; ci < c; ci++) {
        result[ri][ci] = mat[k / cols][k % cols];
        k++;
      }
    }
    return result;
  }

  public int[][] matrixReshape(int[][] mat, int r, int c) {
    int rows = mat.length;
    int cols = mat[0].length;
    int total = rows * cols;
    if (r * c != total) {
      return mat;
    }
    int[][] result = new int[r][c];
    for (int i = 0; i < total; i++) {
      result[i / c][i % c] = mat[i / cols][i % cols];
    }
    return result;
  }

  // 530. 二叉搜索树的最小绝对差
  public int getMinimumDifference(TreeNode root) {
    doGetMinimumDifference(root);
    return minimumDifference;
  }

  private void doGetMinimumDifference(TreeNode root) {
    if (root == null) {
      return;
    }
    doGetMinimumDifference(root.left);
    updateMinimumDifference(root.val);
    doGetMinimumDifference(root.right);
  }

  private void updateMinimumDifference(int val) {
    if (preEle == -1) {
      preEle = val;
      return;
    }
    minimumDifference = Math.min(minimumDifference, val - preEle);
    preEle = val;
  }

  // 501. 二叉搜索树中的众数
  public int[] findMode(TreeNode root) {
    Map<Integer, Integer> map = new HashMap<>();
    fillMap(root, map);
    Stack<Map.Entry<Integer, Integer>> stack = new Stack<>();
    for (Map.Entry<Integer, Integer> e : map.entrySet()) {
      if (stack.empty()) {
        stack.push(e);
        continue;
      }
      int diff = stack.peek().getValue().compareTo(e.getValue());
      if (diff == 0) {
        stack.push(e);
        continue;
      }
      if (diff < 0) {
        stack.clear();
        stack.push(e);
      }
    }
    int[] result = new int[stack.size()];
    for (int i = 0; i < result.length; i++) {
      result[i] = stack.pop().getKey();
    }
    return result;
  }

  private void fillMap(TreeNode root, Map<Integer, Integer> map) {
    if (root == null) {
      return;
    }
    map.put(root.val, map.getOrDefault(root.val, 0) + 1);
    fillMap(root.left, map);
    fillMap(root.right, map);
  }

  // 404. 左叶子之和
  public int sumOfLeftLeaves(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    doSumOfLeftLeaves(root, list);
    int sum = 0;
    for (Integer n : list) {
      sum += n;
    }
    return sum;
  }

  private void doSumOfLeftLeaves(TreeNode root, List<Integer> list) {
    if (root == null) {
      return;
    }
    TreeNode leftLeaf = root.left;
    if (leftLeaf == null) {
      doSumOfLeftLeaves(root.right, list);
      return;
    }
    if (leftLeaf.left == null && leftLeaf.right == null) {
      list.add(leftLeaf.val);
    }
    doSumOfLeftLeaves(leftLeaf, list);
    doSumOfLeftLeaves(root.right, list);
  }

  // 257. 二叉树的所有路径
  public List<String> binaryTreePaths(TreeNode root) {
    List<String> list = new ArrayList<>();
    doBinaryTreePaths(root, list, "");
    return list;
  }

  private void doBinaryTreePaths(TreeNode root, List<String> list, String already) {
    if (root == null) {
      return;
    }
    StringBuilder builder = new StringBuilder(already).append(root.val);
    if (root.left == null && root.right == null) {
      list.add(builder.toString());
      return;
    }
    builder.append("->");
    doBinaryTreePaths(root.left, list, builder.toString());
    doBinaryTreePaths(root.right, list, builder.toString());
  }

  // 2347. 最好的扑克手牌
  public String bestHand(int[] ranks, char[] suits) {
    boolean condition3 = false;
    Set<Integer> rankSet = new HashSet<>();
    int[] suitCount = new int[4];
    int[] rankCount = new int[14];
    for (int i = 0; i < 5; i++) {
      if (++suitCount[suits[i] - 'a'] >= 5) {
        return "Flush";
      }
      if (++rankCount[ranks[i]] >= 3) {
        return "Three of a Kind";
      }
      if (rankCount[ranks[i]] >= 2) {
        condition3 = true;
      }
      rankSet.add(ranks[i]);
    }
    return condition3 ? "Pair" : (rankSet.size() >= 5 ? "High Card" : "");
  }

  // 697. 数组的度
  public int findShortestSubArray(int[] nums) {
    Map<Integer, ArrayDegreeHelper> helperMap = new HashMap<>();
    ArrayDegreeHelper expected = null;
    int len = nums.length;
    for (int i = 0; i < len; i++) {
      ArrayDegreeHelper helper = helperMap.get(nums[i]);
      if (helper == null) {
        helper = new ArrayDegreeHelper(nums[i], i);
        helperMap.put(nums[i], helper);
      } else {
        helper.update(i);
      }
      if (expected == null || helper.count > expected.count || (helper.count == expected.count && helper.rangeLength < expected.rangeLength)) {
        expected = helper;
      }
    }
    return expected.rangeLength;
  }

  class ArrayDegreeHelper {
    int val;
    int count;
    int start;
    int rangeLength;

    public ArrayDegreeHelper(int val, int startIndex) {
      this.val = val;
      this.start = startIndex;
      this.count = 1;
      this.rangeLength = 1;
    }

    public void update(int index) {
      this.rangeLength = index - start + 1;
      this.count++;
    }
  }

  // 680. 验证回文串 II
  public boolean validPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j && s.charAt(i) == s.charAt(j)) {
      i++;
      j--;
    }
    return isHuiwen(s, i + 1, j) || isHuiwen(s, i, j - 1);
  }

  private boolean isHuiwen(String s, int i, int j) {
    while (i < j) {
      if (s.charAt(i++) != s.charAt(j--)) {
        return false;
      }
    }
    return true;
  }

  // 682. 棒球比赛
  public int calPoints(String[] operations) {
    int len = operations.length;
    int[] result = new int[len];
    int index = 0;
    for (String operation : operations) {
      if ("C".equals(operation)) {
        index--;
        continue;
      }
      if ("+".equals(operation)) {
        result[index] = result[index - 1] + result[index - 2];
      } else if ("D".equals(operation)) {
        result[index] = (result[index - 1] << 1);
      } else {
        result[index] = Integer.parseInt(operation);
      }
      index++;
    }
    int sum = 0;
    for (int i = index - 1; i >= 0; i--) {
      sum += result[i];
    }
    return sum;
  }

  // 696. 计数二进制子串
  public int countBinarySubstrings(String s) {
    char[] chars = s.toCharArray();
    int len = chars.length;
    int preCount = 0, currCount, start = 0, sum = 0;
    for (int i = 1; i < len; i++) {
      if (chars[i] != chars[i - 1]) {
        currCount = i - start;
        sum += Math.min(preCount, currCount);
        preCount = currCount;
        start = i;
      }
    }
    sum += Math.min(preCount, len - start);
    return sum;
  }

  // 492. 构造矩形
  public int[] constructRectangle(int area) {
    for (int i = (int) Math.sqrt(area); i >= 1; i--) {
      if (area % i == 0) {
        return new int[]{area / i, i};
      }
    }
    return null;
  }

  // 463. 岛屿的周长
  public int islandPerimeter(int[][] grid) {
    int rows = grid.length;
    int cols = grid[0].length;
    int sum = 0, curr;
    for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) {
        if (grid[i][j] == 0) {
          continue;
        }
        curr = 4;
        if (i > 0 && grid[i - 1][j] == 1) {
          curr--;
        }
        if (i < rows - 1 && grid[i + 1][j] == 1) {
          curr--;
        }
        if (j > 0 && grid[i][j - 1] == 1) {
          curr--;
        }
        if (j < cols - 1 && grid[i][j + 1] == 1) {
          curr--;
        }
        sum += curr;
      }
    }
    return sum;
  }

  // 709. 转换成小写字母
  public String toLowerCase(String s) {
    char[] chars = s.toCharArray();
    int len = chars.length;
    for (int i = 0; i < len; i++) {
      if (chars[i] >= 'A' && chars[i] <= 'Z') {
        chars[i] = (char) (chars[i] | 0x20);
      }
    }
    return new String(chars);
  }

  // 997. 找到小镇的法官
  public int findJudge(int n, int[][] trust) {
    if (n == 1) {
      return 1;
    }
    Map<Integer, Integer> beTrusted = new HashMap<>();
    Set<Integer> notCandidate = new HashSet<>();
    for (int[] p : trust) {
      beTrusted.put(p[1], beTrusted.getOrDefault(p[1], 0) + 1);
      notCandidate.add(p[0]);
    }
    for (Map.Entry<Integer, Integer> e : beTrusted.entrySet()) {
      if (e.getValue() == n - 1 && !notCandidate.contains(e.getKey())) {
        return e.getKey();
      }
    }
    return -1;
  }

  // 905. 按奇偶排序数组
  public int[] sortArrayByParity(int[] nums) {
    int i = 0, j = nums.length - 1;
    while (i < j) {
      if ((nums[i] & 1) == 0) {
        i++;
        continue;
      }
      if ((nums[j] & 1) == 1) {
        j--;
        continue;
      }
      nums[i] = nums[i] << 0x10 | nums[j];
      nums[j] = nums[i] >> 0x10;
      nums[i] = nums[i] & 0xffff;
    }
    return nums;
  }


  // 剑指 Offer 40. 最小的k个数
  public int[] getLeastNumbers(int[] arr, int k) {
    Arrays.sort(arr);
    return Arrays.copyOfRange(arr, 0, k);
  }

  // 557. 反转字符串中的单词 III
  public String reverseWords(String s) {
    char[] chars = s.toCharArray();
    int len = chars.length, i = 0, j, x;
    for (int index = 0; index < len; index++) {
      if (index >= len - 1 || chars[index + 1] == ' ') {
        for (j = index; i < j; i++, j--) {
          x = chars[i] << 8 | chars[j];
          chars[j] = (char) (x >> 8);
          chars[i] = (char) (x & 0xff);
        }
        i = index + 2;
      }
    }
    return new String(chars);
  }

  // 剑指 Offer 22. 链表中倒数第k个节点
  public ListNode getKthFromEnd(ListNode head, int k) {
    List<ListNode> list = new ArrayList<>();
    ListNode t = head;
    while (t != null) {
      list.add(t);
      t = t.next;
    }
    int size = list.size(); // 6
    // k=2
    // 0 1 2 3 4 5  ==>4=6-2
    int index = size - k;
    return (index >= 0 && index < size) ? list.get(index) : null;
  }

  // 面试题 10.01. 合并排序的数组
  public void merge_copy(int[] A, int m, int[] B, int n) {
    int maxIndex = m + n - 1;
    int i = m - 1, j = n - 1;
    for (int index = maxIndex; index >= 0 && i >= 0 && j >= 0; index--) {
      if (A[i] > B[j]) {
        A[index] = A[i--];
      } else {
        A[index] = B[j--];
      }
    }
    if (j >= 0) {
      System.arraycopy(B, 0, A, 0, j + 1);
    }
  }

  // 977. 有序数组的平方
  public int[] sortedSquares(int[] nums) {
    int len = nums.length;
    int[] arr = new int[len];
    int firstNotNegativeIndex = 0;
    for (; firstNotNegativeIndex < len; firstNotNegativeIndex++) {
      if (nums[firstNotNegativeIndex] >= 0) {
        break;
      }
    }
    int left = firstNotNegativeIndex - 1, right = firstNotNegativeIndex;
    for (int k = 0; k < len; k++) {
      if (left >= 0 && (right >= len || -nums[left] <= nums[right])) {
        arr[k] = (int) Math.pow(nums[left--], 2);
        continue;
      }
      if (right < len && (left < 0 || -nums[left] > nums[right])) {
        arr[k] = (int) Math.pow(nums[right++], 2);
      }
    }
    return arr;
  }

  // 704. 二分查找
  public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    if (nums[right] == target) {
      return right;
    }
    int middle;
    while (right - left > 1) {
      middle = left + ((right - left) >> 1);
      if (nums[middle] <= target) {
        left = middle;
      } else {
        right = middle;
      }
    }
    return nums[left] == target ? left : -1;
  }

  // 2341. 数组能形成多少数对
  public int[] numberOfPairs1(int[] nums) {
    int[] times = new int[101];
    for (int n : nums) {
      times[n]++;
    }
    int pairs = 0, left = 0;
    for (int time : times) {
      if (time <= 0) {
        continue;
      }
      left += (time & 1);
      pairs += (time >> 1);
    }
    return new int[]{pairs, left};
  }

  public int[] numberOfPairs(int[] nums) {
    int[] times = new int[101];
    for (int n : nums) {
      times[n]++;
    }
    int oddTimesCount = 0;
    for (int time : times) {
      oddTimesCount += (time & 1);
    }
    return new int[]{(nums.length - oddTimesCount) >> 1, oddTimesCount};
  }

  // 561. 数组拆分
  public int arrayPairSum(int[] nums) {
    Arrays.sort(nums);
    int len = nums.length;
    int sum = 0;
    for (int i = 0; i < len; i += 2) {
      sum += nums[i];
    }
    return sum;
  }

  // 551. 学生出勤记录 I
  public boolean checkRecord(String s) {
    char[] chars = s.toCharArray();
    int len = chars.length;
    if (len < 3) {
      return !"AA".equals(s);
    }
    int absentDays = 0;
    int end = len - 2;
    for (int i = 0; i < end; i++) {
      if (chars[i] == 'A' && absentDays++ >= 1) {
        return false;
      }
      if (chars[i] == 'L' && chars[i + 1] == 'L' && chars[i + 2] == 'L') {
        return false;
      }
    }
    return true;
  }

  // 409. 最长回文串
  public int longestPalindrome(String s) {
    int len = s.length();
    int[] times = new int[123];
    for (int i = 0; i < len; i++) {
      times[s.charAt(i)]++;
    }
    int oddCount = 0;
    for (int time : times) {
      if ((time & 1) == 1) {
        oddCount++;
      }
    }
    return len + (oddCount == 0 ? 0 : 1 - oddCount);
  }

  // 392. 判断子序列
  public boolean isSubsequence(String s, String t) {
    int len = t.length();
    char c, j = 0;
    for (int i = 0; i < s.length(); i++, j++) {
      c = s.charAt(i);
      while (j < len && t.charAt(j) != c) {
        j++;
      }
      if (j >= len) {
        return false;
      }
    }
    return true;
  }

  // 2133. 检查是否每一行每一列都包含全部整数
  public boolean checkValid(int[][] matrix) {
    int len = matrix.length;
    Set<Integer> rowElements = new HashSet<>();
    Set<Integer> colElements = new HashSet<>();
    for (int i = 0; i < len; i++) {
      rowElements.clear();
      colElements.clear();
      for (int j = 0; j < len; j++) {
        rowElements.add(matrix[i][j]);
        colElements.add(matrix[j][i]);
      }
      if (rowElements.size() != len || colElements.size() != len) {
        return false;
      }
    }
    return true;
  }

  // 500. 键盘行
  public String[] findWords(String[] words) {
    int[] indices = new int[]{2, 3, 3, 2, 1, 2, 2, 2, 1, 2, 2, 2, 3, 3, 1, 1, 1, 1, 2, 1, 1, 3, 1, 3, 1, 3};
    List<String> list = new ArrayList<>();
    char[] chars;
    label:
    for (String word : words) {
      chars = word.toCharArray();
      for (int i = 1; i < chars.length; i++) {
        if (indices[chars[i] >= 'a' ? (chars[i] - 'a') : (chars[i] - 'A')] != indices[chars[i - 1] >= 'a' ? (chars[i - 1] - 'a') : (chars[i - 1] - 'A')]) {
          continue label;
        }
      }
      list.add(word);
    }
    return list.toArray(new String[0]);
  }

  // 459. 重复的子字符串
  public boolean repeatedSubstringPattern(String s) {
    return (s + s).indexOf(s, 1) != s.length();
  }

  // 415. 字符串相加
  public String addStrings(String num1, String num2) {
    StringBuilder builder = new StringBuilder();
    int len1 = num1.length();
    int len2 = num2.length();
    int[] arr1 = new int[len1];
    int[] arr2 = new int[len2];
    for (int i = 0; i < len1; i++) {
      arr1[i] = num1.charAt(i) - '0';
    }
    for (int i = 0; i < len2; i++) {
      arr2[i] = num2.charAt(i) - '0';
    }
    int over = 0, sum;
    int i = len1 - 1, j = len2 - 1;
    for (; i >= 0 && j >= 0; i--, j--) {
      sum = arr1[i] + arr2[j] + over;
      over = sum / 10;
      builder.append(sum % 10);
    }
    if (i >= 0) {
      for (int k = i; k >= 0; k--) {
        sum = arr1[k] + over;
        over = sum / 10;
        builder.append(sum % 10);
      }
    } else if (j >= 0) {
      for (int k = j; k >= 0; k--) {
        sum = arr2[k] + over;
        over = sum / 10;
        builder.append(sum % 10);
      }
    }
    if (over > 0) {
      builder.append(over);
    }
    return builder.reverse().toString();
  }

  // 234. 回文链表
  public boolean isPalindrome(ListNode head) {
    List<Integer> list = new ArrayList<>();
    ListNode t = head;
    while (t != null) {
      list.add(t.val);
      t = t.next;
    }
    int i = 0, j = list.size() - 1;
    while (i < j) {
      if (!list.get(i).equals(list.get(j))) {
        return false;
      }
      i++;
      j--;
    }
    return true;
  }

  // 206. 反转链表(不改变原链表，返回一个新的链表)
  public ListNode reverseList1(ListNode head) {
    if (head == null) {
      return null;
    }
    ListNode result = new ListNode(head.val);
    ListNode t = head.next;
    while (t != null) {
      result = new ListNode(t.val, result);
      t = t.next;
    }
    return result;
  }

  // 206. 反转链表(修改原链表)
  public ListNode reverseList(ListNode head) {
    if (head == null) {
      return null;
    }
    ListNode pre = head, $next = head.next;
    pre.next = null;
    ListNode t = $next;
    while (t != null) {
      $next = t.next;
      t.next = pre;
      pre = t;
      t = $next;
    }
    return pre;
  }

  // 203. 移除链表元素
  public ListNode removeElements(ListNode head, int val) {
    ListNode virtualHead = new ListNode(-1, head);
    ListNode t = virtualHead;
    while (t.next != null) {
      if (t.next.val == val) {
        t.next = t.next.next;
      } else {
        t = t.next;
      }
    }
    return virtualHead.next;
  }

  // 160. 相交链表
  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) {
      return null;
    }
    ListNode pA = headA;
    ListNode pB = headB;
    while (pA != pB) {
      pA = (pA == null ? headB : pA.next);
      pB = (pB == null ? headA : pB.next);
    }
    return pA;
  }

  // 141. 环形链表
  public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
      return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
      if (fast == null || fast.next == null) {
        return false;
      }
      slow = slow.next;
      fast = fast.next.next;
    }
    return true;
  }

  // 2335. 装满杯子需要的最短总时长
  public int fillCups(int[] amount) {
    Arrays.sort(amount);
    if (amount[2] - amount[0] >= amount[1]) {
      return amount[2];
    }
    return (amount[0] + amount[1] + amount[2] + 1) >> 1;
  }

  // 219. 存在重复元素 II
  public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> set = new HashSet<>(k);
    int length = nums.length;
    for (int i = 0; i < length; i++) {
      if (set.contains(nums[i])) {
        return true;
      }
      set.add(nums[i]);
      if (set.size() > k) {
        set.remove(nums[i - k]);
      }
    }
    return false;
  }

  // 168. Excel表列名称
  public String convertToTitle(int columnNumber) {
    char[] alphabet = new char[26];
    for (int i = 0; i < 26; i++) {
      alphabet[i] = (char) ('A' + i);
    }
    // 1  alphabet[0]  A
    // 25 alphabet[24] Y
    // 26 alphabet[25] Z
    // 27 alphabet[0]  AA
    // 28 alphabet[1]  AB
    // 28=26+2 AB
    // 28=26+3 AC
    // 52=26+26 AZ
    // 53=26*2+1 BA
    // 54=26*2+2 BB
    // 701=26*26+25 ZY
    StringBuilder builder = new StringBuilder();
    while (columnNumber-- > 0) {
      builder.append(alphabet[columnNumber % 26]);
      columnNumber /= 26;
    }
    return builder.reverse().toString();
  }

  // 171. Excel 表列序号
  public int titleToNumber(String columnTitle) {
    int[] arr = new int[]{1, 26, 676, 17576, 456976, 11881376, 308915776};
    int sum = 0;
    int len = columnTitle.length();
    for (int i = 0; i < len; i++) {
      sum += (columnTitle.charAt(len - i - 1) - 'A' + 1) * arr[i];
    }
    return sum;
  }

  // 125. 验证回文串
  public boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
      char c1 = s.charAt(i);
      if (!DIGITAL_OR_ALPHABET[c1]) {
        i++;
        continue;
      }
      char c2 = s.charAt(j);
      if (!DIGITAL_OR_ALPHABET[c2]) {
        j--;
        continue;
      }
      if (Character.toLowerCase(c1) != Character.toLowerCase(c2)) {
        return false;
      }
      i++;
      j--;
    }
    return true;
  }

  // 112. 路径总和
  public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) {
      return false;
    }
    if (root.left == null && root.right == null) {
      return targetSum == root.val;
    }
    int diff = targetSum - root.val;
    return hasPathSum(root.left, diff) || hasPathSum(root.right, diff);
  }

  // 110. 平衡二叉树
  public boolean isBalanced(TreeNode root) {
    if (root == null) {
      return true;
    }
    TreeNode myLeft = root.left;
    TreeNode myRight = root.right;
    return Math.abs(maxDepth(myLeft) - maxDepth(myRight)) <= 1 && isBalanced(myLeft) && isBalanced(myRight);
  }

  // 108. 将有序数组转换为二叉搜索树
  public TreeNode sortedArrayToBST(int[] nums) {
    if (nums.length == 1) {
      return new TreeNode(nums[0]);
    }
    if (nums.length == 2) {
      return new TreeNode(nums[0], null, new TreeNode(nums[1]));
    }
    int middle = nums.length >> 1;
    return new TreeNode(nums[middle], sortedArrayToBST(Arrays.copyOfRange(nums, 0, middle)), sortedArrayToBST(Arrays.copyOfRange(nums, middle + 1, nums.length)));
  }

  // 345. 反转字符串中的元音字母
  public String reverseVowels1(String s) {
    Set<Character> set = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));
    char[] chars = s.toCharArray();
    List<Integer> list = Stream.iterate(0, i -> i + 1).limit(chars.length).filter(i -> set.contains(chars[i])).collect(Collectors.toList());
    int size = list.size();
    int endIndex = size >> 1;
    int i1, i2, x;
    for (int i = 0; i < endIndex; i++) {
      i1 = list.get(i);
      i2 = list.get(size - i - 1);
      x = chars[i1] << 0x8 | chars[i2];
      chars[i2] = (char) (x >> 0x8);
      chars[i1] = (char) (x & 0xff);
    }
    return new String(chars);
  }

  public String reverseVowels(String s) {
    boolean[] isVowel = new boolean[128];
    isVowel['a'] = true;
    isVowel['e'] = true;
    isVowel['i'] = true;
    isVowel['o'] = true;
    isVowel['u'] = true;
    isVowel['A'] = true;
    isVowel['E'] = true;
    isVowel['I'] = true;
    isVowel['O'] = true;
    isVowel['U'] = true;
    char[] chars = s.toCharArray();
    int i = 0, j = chars.length - 1;
    int x;
    while (i < j) {
      if (!isVowel[chars[i]]) {
        i++;
        continue;
      }
      if (!isVowel[chars[j]]) {
        j--;
        continue;
      }
      x = chars[i] << 0x8 | chars[j];
      chars[j] = (char) (x >> 0x8);
      chars[i] = (char) (x & 0xff);
      i++;
      j--;
    }
    return new String(chars);
  }

  // 242. 有效的字母异位词
  public boolean isAnagram1(String s, String t) {
    int[] arr1 = new int[26];
    int[] arr2 = new int[26];
    for (int i = 0; i < s.length(); i++) {
      arr1[s.charAt(i) - 'a']++;
    }
    for (int i = 0; i < t.length(); i++) {
      arr2[t.charAt(i) - 'a']++;
    }
    for (int i = 0; i < 26; i++) {
      if (arr1[i] != arr2[i]) {
        return false;
      }
    }
    return true;
  }

  public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) {
      return false;
    }
    int[] arr = new int[26];
    for (int i = 0; i < s.length(); i++) {
      arr[s.charAt(i) - 'a']++;
    }
    for (int i = 0; i < t.length(); i++) {
      if (--arr[t.charAt(i) - 'a'] < 0) {
        return false;
      }
    }
    return true;
  }

  // 217. 存在重复元素
  public boolean containsDuplicate(int[] nums) {
    return IntStream.of(nums).distinct().count() != nums.length;
  }

  // 205. 同构字符串
  public boolean isIsomorphic(String s, String t) {
    char[] sToT = new char[128];
    char[] tToS = new char[128];
    int len = s.length();
    char sChar, tChar;
    for (int i = 0; i < len; i++) {
      sChar = s.charAt(i);
      tChar = t.charAt(i);
      if ((sToT[sChar] != 0 && sToT[sChar] != tChar) || (tToS[tChar] != 0 && tToS[tChar] != sChar)) {
        return false;
      }
      sToT[sChar] = tChar;
      tToS[tChar] = sChar;
    }
    return true;
  }

  // 190. 颠倒二进制位
  public int reverseBits1(int n) {
    int k = 0;
    for (int i = 0; i < 32; i++) {
      k |= (n & 1) << (31 - i);
      n >>= 1;
    }
    return k;
  }

  public int reverseBits(int n) {
    // mask1 = 0101 0101 0101 0101 0101 0101 0101 0101
    int mask1 = 0x55555555;
    // mask2 = 0011 0011 0011 0011 0011 0011 0011 0011
    int mask2 = 0x33333333;
    // mask4 = 0000 1111 0000 1111 0000 1111 0000 1111
    int mask4 = 0x0f0f0f0f;
    // mask8 = 0000 0000 1111 1111 0000 0000 1111 1111
    int mask8 = 0x00ff00ff;
    // mask16 = 0000 0000 0000 0000 1111 1111 1111 1111
    int mask16 = 0x0000ffff;
    n = ((n & mask1) << 1) | ((n >> 1) & mask1);
    n = ((n & mask2) << 2) | ((n >> 2) & mask2);
    n = ((n & mask4) << 4) | ((n >> 4) & mask4);
    n = ((n & mask8) << 8) | ((n >> 8) & mask8);
    return ((n & mask16) << 16) | ((n >> 16) & mask16);
  }

  // 104. 二叉树的最大深度
  public int maxDepth(TreeNode root) {
    if (root == null) {
      return 0;
    }
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
  }

  // 101. 对称二叉树
  public boolean isSymmetric(TreeNode root) {
    return doIsSameTree(root.left, root.right);
  }

  // 520. 检测大写字母
  public boolean detectCapitalUse(String word) {
    int k = 0;
    int len = word.length();
    int offset = len - 1;
    for (int i = 0; i < len; i++) {
      k |= (word.charAt(i) >= 'a' ? 0 : 1) << (offset - i);
    }
    return k == 0 || k == (1 << offset) || k == (1 << len) - 1;
  }

  // 495. 提莫攻击
  public int findPoisonedDuration1(int[] timeSeries, int duration) {
    int sum = duration;
    int len = timeSeries.length;
    if (len == 1) {
      return sum;
    }
    for (int i = 1; i < len; i++) {
      sum += Math.min(timeSeries[i] - timeSeries[i - 1], duration);
    }
    return sum;
  }

  public int findPoisonedDuration(int[] timeSeries, int duration) {
    int expired = 0, sum = 0;
    for (int t : timeSeries) {
      if (t >= expired) {
        sum += duration;
      } else {
        sum += (t + duration - expired);
      }
      expired = t + duration;
    }
    return sum;
  }

  // 509. 斐波那契数
  public int fib(int n) {
    if (n == 0 || n == 1) {
      return n;
    }
    int i = 0, j = 1, tmp;
    for (int k = 2; k < n; k++) {
      tmp = j;
      j = i + j;
      i = tmp;
    }
    return i + j;
  }

  // 507. 完美数
  public boolean checkPerfectNumber(int num) {
    if (num == 1) {
      return false;
    }
    int endIndex = (int) Math.sqrt(num);
    int diff = num - 1;
    for (int i = 2; i <= endIndex; i++) {
      if (num % i == 0) {
        diff -= (i + num / i);
      }
    }
    // return num == 6 || num == 28 || num == 496 || num == 8128 || num == 33550336;
    return diff == 0;
  }

  // 504. 七进制数
  public String convertToBase7(int num) {
    if (num == 0) {
      return "0";
    }
    if (num < 0) {
      return "-" + convertToBase7(-num);
    }
    StringBuilder builder = new StringBuilder();
    while (num != 0) {
      builder.append(num % 7);
      num /= 7;
    }
    // return Integer.toString(num, 7);
    return builder.reverse().toString();
  }

  // 441. 排列硬币
  public int arrangeCoins1(int n) {
    int pre = 1;
    int times = 1, curr;
    for (int i = 2; true; i++) {
      curr = pre + i;
      if (curr - n > 0) {
        return times;
      }
      pre = curr;
      times++;
    }
  }

  public int arrangeCoins2(int n) {
    int result = 0;
    while (n - result > 0) {
      n -= ++result;
    }
    return result;
  }

  public int arrangeCoins(int n) {
    return ((int) Math.sqrt(1 + ((long) n << 3)) - 1) >> 1;
  }

  // 496. 下一个更大元素 I
  public int[] nextGreaterElement1(int[] nums1, int[] nums2) {
    int len2 = nums2.length;
    Map<Integer, Integer> map = new HashMap<>(len2);
    for (int i = 0; i < len2; i++) {
      map.put(nums2[i], i);
    }
    int len1 = nums1.length;
    int[] arr = new int[len1];
    Integer targetIndex;
    for (int i = 0; i < len1; i++) {
      arr[i] = -1;
      targetIndex = map.get(nums1[i]);
      if (targetIndex == null) {
        continue;
      }
      for (int j = targetIndex + 1; j < len2; j++) {
        if (nums2[j] > nums1[i]) {
          arr[i] = nums2[j];
          break;
        }
      }
    }
    return arr;
  }

  public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    int len2 = nums2.length;
    Stack<Integer> stack = new Stack<>();
    Map<Integer, Integer> map = new HashMap<>(len2);
    for (int i = len2 - 1; i >= 0; i--) {
      while (!stack.empty() && stack.peek() < nums2[i]) {
        stack.pop();
      }
      if (stack.empty()) {
        map.put(nums2[i], -1);
      } else {
        map.put(nums2[i], stack.peek());
      }
      stack.push(nums2[i]);
    }
    int len1 = nums1.length;
    int[] arr = new int[len1];
    for (int i = 0; i < len1; i++) {
      arr[i] = map.getOrDefault(nums1[i], -1);
    }
    return arr;
  }

  // 434. 字符串中的单词数
  public int countSegments(String s) {
    String[] strings = s.split(" ");
    int count = 0;
    for (String curr : strings) {
      if (!"".equals(curr.trim())) {
        count++;
      }
    }
    return count;
  }

  // 461. 汉明距离
  public int hammingDistance(int x, int y) {
    int k = (x ^ y);
    int count = 0;
    while (k != 0) {
      k &= (k - 1);
      count++;
    }
    return Integer.bitCount(x ^ y);
  }

  // 482. 密钥格式化
  public String licenseKeyFormatting(String s, int k) {
    List<Character> list = new ArrayList<>();
    StringBuilder builder = new StringBuilder();
    int len = s.length();
    char c;
    for (int i = 0; i < len; i++) {
      c = s.charAt(i);
      if (c != '-') {
        list.add(c >= 'a' ? (char) (c - 32) : c);
      }
    }
    int firstEnd = list.size() % k;
    for (int i = 0; i < firstEnd; i++) {
      builder.append(list.get(i));
    }
    if (list.size() < k) {
      return builder.toString();
    }
    if (firstEnd > 0) {
      builder.append('-');
    }
    for (int i = firstEnd; i < list.size(); i++) {
      builder.append(list.get(i));
      if ((i - firstEnd + 1) % k == 0 && i < list.size() - 1) {
        builder.append('-');
      }
    }
    return builder.toString();
  }

  // 485. 最大连续 1 的个数
  public int findMaxConsecutiveOnes(int[] nums) {
    int count = 0;
    int max = count;
    for (int n : nums) {
      if (n == 1) {
        count++;
      } else {
        if (count > max) {
          max = count;
        }
        count = 0;
      }
    }
    return Math.max(count, max);
  }

  // 455. 分发饼干
  public int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);
    Arrays.sort(s);
    int len1 = g.length;
    int len2 = s.length;
    int i = 0, j = 0;
    while (i < len1 && j < len2) {
      if (s[j] >= g[i]) {
        i++;
      }
      j++;
    }
    return i;
  }

  // 448. 找到所有数组中消失的数字
  public List<Integer> findDisappearedNumbers1(int[] nums) {
    Arrays.sort(nums);
    List<Integer> list = new ArrayList<>();
    int left = nums[0];
    for (int i = 1; i < left; i++) {
      list.add(i);
    }
    int len = nums.length;
    for (int i = 1; i < len; i++) {
      for (int j = left + 1; j < nums[i]; j++) {
        list.add(j);
      }
      left = nums[i];
    }
    for (int i = nums[len - 1] + 1; i <= len; i++) {
      list.add(i);
    }
    return list;
  }

  public List<Integer> findDisappearedNumbers(int[] nums) {
    int len = nums.length;
    int[] correct = new int[len];
    for (int n : nums) {
      correct[n - 1]++;
    }
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < len; i++) {
      if (correct[i] == 0) {
        list.add(i + 1);
      }
    }
    return list;
  }

  // 1604. 警告一小时内使用相同员工卡大于等于三次的人
  public List<String> alertNames(String[] keyName, String[] keyTime) {
    int len = keyName.length;
    if (len < 3) {
      return Collections.emptyList();
    }
    Map<String, List<Integer>> map = new HashMap<>();
    List<Integer> minuteStamps;
    String[] hourMinute;
    int minute;
    for (int i = 0; i < len; i++) {
      minuteStamps = map.get(keyName[i]);
      hourMinute = keyTime[i].split(":");
      minute = Integer.parseInt(hourMinute[0]) * 60 + Integer.parseInt(hourMinute[1]);
      if (minuteStamps == null) {
        minuteStamps = new ArrayList<>();
        minuteStamps.add(minute);
        map.put(keyName[i], minuteStamps);
      } else {
        minuteStamps.add(minute);
      }
    }
    int size, diff;
    Set<String> users = new TreeSet<>(Comparator.comparingInt(String::length).thenComparing(o -> o));
    for (String name : map.keySet()) {
      minuteStamps = map.get(name);
      Collections.sort(minuteStamps);
      size = minuteStamps.size();
      if (size < 3) {
        continue;
      }
      for (int i = 0; i < size - 2; i++) {
        diff = minuteStamps.get(i + 2) - minuteStamps.get(i);
        if (diff > 0 && diff <= 60) {
          users.add(name);
        }
      }
    }
    return new ArrayList<>(users);
  }

  class TimePair {
    int range;
    int times;
  }

  // 476. 数字的补数
  public int findComplement(int num) {
    int k = num;
    k |= k >> 1;
    k |= k >> 2;
    k |= k >> 4;
    k |= k >> 8;
    k |= k >> 16;
    return (~num) & k;
  }

  // 2331. 计算布尔二叉树的值
  public boolean evaluateTree(TreeNode root) {
    if (root.left == null) {
      return root.val == 1;
    }
    boolean calculateLeft = evaluateTree(root.left);
    boolean calculateRight = evaluateTree(root.right);
    return root.val == 2 ? (calculateLeft || calculateRight) : (calculateLeft && calculateRight);
  }

  // 228. 汇总区间
  public List<String> summaryRanges(int[] nums) {
    int len = nums.length;
    int i = 0, start;
    List<String> list = new ArrayList<>();
    StringBuilder builder;
    while (i < len) {
      start = i;
      i++;
      while (i < len && nums[i] == nums[i - 1] + 1) {
        i++;
      }
      builder = new StringBuilder();
      builder.append(nums[start]);
      if (start < i - 1) {
        builder.append("->").append(nums[i - 1]);
      }
      list.add(builder.toString());
    }
    return list;
  }

  // 202. 快乐数
  public boolean isHappy1(int n) {
    Set<Integer> numbers = new HashSet<>();
    int k;
    while (n != 1 && !numbers.contains(n)) {
      numbers.add(n);
      k = 0;
      while (n > 0) {
        k += Math.pow(n % 10, 2);
        n /= 10;
      }
      n = k;
    }
    return n == 1;
  }

  public boolean isHappy(int n) {
    int lower = n, faster = n;
    int k;
    do {
      k = 0;
      while (lower > 0) {
        k += Math.pow(lower % 10, 2);
        lower /= 10;
      }
      lower = k;
      k = 0;
      while (faster > 0) {
        k += Math.pow(faster % 10, 2);
        faster /= 10;
      }
      faster = k;
      k = 0;
      while (faster > 0) {
        k += Math.pow(faster % 10, 2);
        faster /= 10;
      }
      faster = k;
    } while (lower != faster);
    return faster == 1;
  }

  // 169. 多数元素
  public int majorityElement(int[] nums) {
    int candidate = nums[0], count = 0;
    for (int n : nums) {
      if (count == 0) {
        candidate = n;
      }
      count += (n == candidate) ? 1 : -1;
    }
    return candidate;
  }

  // 344. 反转字符串
  public void reverseString1(char[] s) {
    char tmp;
    int len = s.length - 1;
    int middle = (s.length >> 1);
    for (int i = 0; i < middle; i++) {
      tmp = s[i];
      s[i] = s[len - i];
      s[len - i] = tmp;
    }
  }

  public void reverseString(char[] s) {
    int symmetry, x;
    for (int i = 0; i < (s.length >> 1); i++) {
      symmetry = s.length - 1 - i;
      x = s[i] << 0x10 | s[symmetry];
      s[symmetry] = (char) (x >> 0x10);
      s[i] = (char) (x & 0xffff);
    }
  }

  // 541. 反转字符串 II
  public String reverseStr(String s, int k) {
    char[] chars = s.toCharArray();
    int groupCount = (k << 1);
    int len = chars.length;
    for (int i = 0; i < len; i += groupCount) {
      swapChar(chars, i, Math.min(i + k - 1, len - 1));
    }
    return new String(chars);
  }

  private void swapChar(char[] chars, int start, int end) {
    int x;
    while (start < end) {
      x = chars[start] << 8 | chars[end];
      chars[end--] = (char) (x >> 8);
      chars[start++] = (char) (x & 0xff);
    }
  }

  // 283. 移动零
  public void moveZeroes1(int[] nums) {
    int len = nums.length;
    for (int i = 0; i < len - 1; i++) {
      for (int j = 0; j < len - 1 - i; j++) {
        if (nums[j] == 0) {
          nums[j] = nums[j + 1];
          nums[j + 1] = 0;
        }
      }
    }
  }

  public void moveZeroes(int[] nums) {
    int len = nums.length;
    int k = 0, tmp;
    for (int i = 0; i < len; i++) {
      if (nums[i] == 0) {
        continue;
      }
      tmp = nums[i];
      nums[i] = nums[k];
      nums[k++] = tmp;
    }
  }

  // 278. 第一个错误的版本
  public int firstBadVersion(int n) {
    if (n == 1) {
      return 1;
    }
    int min = 1, max = n;
    int middle;
    while (min < max) {
      middle = min + ((max - min) >> 1);
      if (isBadVersion(middle)) {
        max = middle;
      } else {
        min = middle + 1;
      }
    }
    return min;
  }

  private boolean isBadVersion(int version) {
    return version >= 2;
  }

  // 263. 丑数
  public boolean isUgly(int n) {
    if (n <= 0) {
      return false;
    }
    if (n == 1) {
      return true;
    }
    while (n > 1) {
      if ((n & 1) == 0) {
        n >>= 1;
        continue;
      }
      if (n % 3 == 0) {
        n /= 3;
        continue;
      }
      if (n % 5 == 0) {
        n /= 5;
        continue;
      }
      return false;
    }
    return true;
  }

  // 414. 第三大的数
  public int thirdMax1(int[] nums) {
    Integer first = null, second = null, third = null;
    Set<Integer> set = new HashSet<>();
    for (int n : nums) {
      if (set.contains(n)) {
        continue;
      }
      set.add(n);
      if (first == null || n > first) {
        third = second;
        second = first;
        first = n;
        continue;
      }
      if (second == null || n > second) {
        third = second;
        second = n;
        continue;
      }
      if (third == null || n > third) {
        third = n;
      }
    }
    System.out.println(first + " -> " + second + " -> " + third);
    return third == null ? first : third;
  }

  public int thirdMax(int[] nums) {
    Arrays.sort(nums);
    int len = nums.length;
    Set<Integer> set = new HashSet<>();
    for (int i = len - 1; i >= 0; i--) {
      set.add(nums[i]);
      if (set.size() >= 3) {
        return nums[i];
      }
    }
    return nums[len - 1];
  }

  // 412. Fizz Buzz
  public List<String> fizzBuzz(int n) {
    List<String> list = new ArrayList<>(n);
    for (int i = 1; i <= n; i++) {
      if (i % 15 == 0) {
        list.add("FizzBuzz");
        continue;
      }
      if (i % 3 == 0) {
        list.add("Fizz");
        continue;
      }
      if (i % 5 == 0) {
        list.add("Buzz");
        continue;
      }
      list.add(String.valueOf(i));
    }
    return list;
  }

  // 290. 单词规律
  public boolean wordPattern(String pattern, String s) {
    char[] patternChars = pattern.toCharArray();
    String[] sChars = s.split(" ");
    int len = patternChars.length;
    if (sChars.length != len) {
      return false;
    }
    // 建立 pattern -> s 的映射关系，且要保证是双射，即必须是“一对一”，不能“多对一”
    Map<Character, String> map = new HashMap<>();
    String saved;
    for (int i = 0; i < len; i++) {
      saved = map.get(patternChars[i]);
      // 1. 保证充分性。即原像到像的唯一性
      if (saved != null && !saved.equals(sChars[i])) {
        return false;
      }
      // 2. 保证必要性。即像到原像也要保证唯一性
      if (saved == null && map.containsValue(sChars[i])) {
        return false;
      }
      map.put(patternChars[i], sChars[i]);
    }
    return true;
  }

  // 405. 数字转换为十六进制数
  public String toHex(int num) {
    if (num >= 0 && num < 16) {
      return HEX_ELEMENTS[num] + "";
    }
    StringBuilder builder = new StringBuilder();
    boolean wait = true;
    for (int i = 7; i >= 0; i--) {
      int ele = (num >> (i << 2)) & 0xf;
      if (ele != 0 && wait) {
        wait = false;
      }
      if (wait) {
        continue;
      }
      builder.append(HEX_ELEMENTS[ele]);
    }
    return builder.toString();
  }

  // 387. 字符串中的第一个唯一字符
  public int firstUniqChar(String s) {
    char[] chars = s.toCharArray();
    int len = chars.length;
    int[] times = new int[26];
    for (char c : chars) {
      times[c - 'a']++;
    }
    for (int i = 0; i < len; i++) {
      if (times[chars[i] - 'a'] == 1) {
        return i;
      }
    }
    return -1;
  }

  // 389. 找不同
  public char findTheDifference(String s, String t) {
    char[] sChars = s.toCharArray();
    char[] tChars = t.toCharArray();
    int k = 0;
    for (char c : sChars) {
      k ^= c;
    }
    for (char c : tChars) {
      k ^= c;
    }
    return ((char) k);
  }

  // 401. 二进制手表
  public List<String> readBinaryWatch(int turnedOn) {
    List<String> list = new ArrayList<>();
    if (turnedOn > 8) {
      return list;
    }
    for (int i = 0; i <= turnedOn; i++) {
      if (i > 3 || (turnedOn - i) > 5) {
        continue;
      }
      int[] hours = HOURS[i];
      int[] minutes = MINUTES[turnedOn - i];
      for (int h : hours) {
        for (int m : minutes) {
          list.add(buildTimeString(h, m));
        }
      }
    }
    return list;
  }

  private static String buildTimeString(int hour, int minute) {
    return hour + ":" + (minute < 10 ? "0" : "") + minute;
  }

  // 326. 3 的幂
  public boolean isPowerOfThree1(int n) {
    if (n < 0) {
      return false;
    }
    while (n > 1) {
      if (n % 3 != 0) {
        return false;
      }
      n /= 3;
    }
    return n == 1;
  }

  public boolean isPowerOfThree(int n) {
    return n > 0 && 1162261467 % n == 0;
  }

  // 342. 4的幂
  public boolean isPowerOfFour(int n) {
    return (n > 0) && ((n & (n - 1)) == 0) && ((n & 0xAAAAAAAA) == 0);
  }

  // 350. 两个数组的交集 II
  public int[] intersect(int[] nums1, int[] nums2) {
    Map<Integer, Integer> map1 = new HashMap<>();
    Map<Integer, Integer> map2 = new HashMap<>();
    for (int i : nums1) {
      map1.put(i, map1.getOrDefault(i, 0) + 1);
    }
    for (int i : nums2) {
      map2.put(i, map2.getOrDefault(i, 0) + 1);
    }
    List<Integer> list = new ArrayList<>();
    for (Integer k : map1.keySet()) {
      if (map2.containsKey(k)) {
        for (int i = 0; i < Math.min(map1.get(k), map2.get(k)); i++) {
          list.add(k);
        }
      }
    }
    return toArray(list);
  }

  // 374. 猜数字大小
  public int guessNumber(int n) {
    int min = 1, max = n, g;
    while (min < max) {
      g = min + ((max - min) >> 1);
      if (guess(g) <= 0) {
        max = g;
      } else {
        min = g + 1;
      }
    }
    return min;
  }

  private int guess(int g) {
    int pick = 1702766719;
    int diff = pick - g;
    return diff == 0 ? 0 : diff / Math.abs(diff);
  }

  // 367. 有效的完全平方数
  public boolean isPerfectSquare(int num) {
    double e = 0.0000005;
    double pre = num;
    double curr;
    while (true) {
      curr = (pre + num / pre) / 2;
      double offset = Math.abs(curr - pre);
      if (offset < e) {
        break;
      }
      pre = curr;
    }
    int bottom = (int) curr;
    return bottom * bottom == num;
  }

  // 2325. 解密消息
  @Deprecated
  public String decodeMessage1(String key, String message) {
    Map<Character, Character> map = new HashMap<>(26);
    map.put(' ', ' ');
    int index = 0;
    char c;
    for (int i = 0; i < key.length(); i++) {
      c = key.charAt(i);
      if (c == ' ' || map.containsKey(c)) {
        continue;
      }
      map.put(c, (char) ('a' + index++));
    }
    int len = message.length();
    char[] chars = new char[len];
    for (int i = 0; i < len; i++) {
      chars[i] = map.get(message.charAt(i));
    }
    return new String(chars);
  }

  public String decodeMessage(String key, String message) {
    char[] table = new char[26];
    int index = 0;
    char c;
    int j;
    for (int i = 0; i < key.length(); i++) {
      c = key.charAt(i);
      j = (c - 'a');
      if (c == ' ' || table[j] != 0) {
        continue;
      }
      table[j] = (char) ('a' + index++);
    }
    int len = message.length();
    char[] chars = new char[len];
    for (int i = 0; i < len; i++) {
      c = message.charAt(i);
      if (c == ' ') {
        chars[i] = ' ';
        continue;
      }
      chars[i] = table[c - 'a'];
    }
    return new String(chars);
  }

  // 349. 两个数组的交集
  public int[] intersection(int[] nums1, int[] nums2) {
    int len = nums1.length;
    Set<Integer> set = new HashSet<>(len);
    for (int j : nums1) {
      set.add(j);
    }
    int len2 = nums2.length;
    if (len2 == 0) {
      return toArray(set);
    }
    Set<Integer> set1 = new HashSet<>(len);
    for (int j : nums2) {
      if (set.contains(j)) {
        set1.add(j);
      }
    }
    return toArray(set1);
  }

  // 268. 丢失的数字
  public int missingNumber(int[] nums) {
    int k = 0;
    int len = nums.length;
    for (int i = 0; i < len; i++) {
      k ^= (i ^ nums[i]);
    }
    k ^= len;
    return k;
  }

  // 231. 2 的幂
  public boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
  }

  // 121. 买卖股票的最佳时机
  public int maxProfit(int[] prices) {
    int min = Integer.MAX_VALUE;
    int maxP = 0;
    int diff;
    for (int price : prices) {
      if (price < min) {
        min = price;
        continue;
      }
      diff = price - min;
      if (diff > maxP) {
        maxP = diff;
      }
    }
    return maxP;
  }

  // 100. 相同的树
  public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
      return true;
    }
    if (p != null && q != null) {
      return doIsSameTree(p, q);
    }
    return false;
  }

  private boolean doIsSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) {
      return true;
    }
    if (p != null && q != null) {
      return (p.val == q.val) && doIsSameTree(p.left, q.left) && doIsSameTree(p.right, q.right);
    }
    return false;
  }

  // 94. 二叉树的中序遍历
  public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    doInorderTraversal(root, list);
    return list;
  }

  public void doInorderTraversal(TreeNode root, List<Integer> list) {
    if (root == null) {
      return;
    }
    doInorderTraversal(root.left, list);
    list.add(root.val);
    doInorderTraversal(root.right, list);
  }

  // 338. 比特位计数
  public int[] countBits(int n, long startTime) {
    int[] arr = new int[n + 1];
    for (int i = 0; i <= n; i++) {
      arr[i] = hammingWeight(i);
    }
    System.out.println("1 cost " + (System.currentTimeMillis() - startTime));
    return arr;
  }

  public int[] countBits2(int n, long startTime) {
    int[] arr = new int[n + 1];
    arr[0] = 0;
    for (int i = 1; i <= n; i++) {
      if ((i & 1) == 1) {
        arr[i] = arr[i - 1] + 1;
        continue;
      }
      arr[i] = arr[(i >> 1)];
    }
    System.out.println("1 cost " + (System.currentTimeMillis() - startTime));
    return arr;
  }

  // 2319. 判断矩阵是否是一个 X 矩阵
  public boolean checkXMatrix(int[][] grid) {
    int len = grid.length;
    int sum = len - 1;
    for (int i = 0; i < len; i++) {
      for (int j = 0; j < len; j++) {
        if ((i == j || i + j == sum) == (grid[i][j] == 0)) {
          return false;
        }
      }
    }
    return true;
  }

  // 1663. 具有给定数值的最小字符串
  public String getSmallestString(int n, int k) {
    int remain = k - n;
    int zCount = remain / 25;
    StringBuilder builder = new StringBuilder();
    if (zCount >= n) {
      return builder.append("z".repeat(n)).toString();
    }
    int otherCharOffset = remain % 25;
    int aCount = n - zCount - 1;
    builder.append("a".repeat(Math.max(0, aCount)));
    builder.append((char) ('a' + otherCharOffset));
    builder.append("z".repeat(Math.max(0, zCount)));
    return builder.toString();
  }

  // 2309. 兼具大小写的最好英文字母
  public String greatestLetter1(String s) {
    Set<Character> set = new HashSet<>();
    for (int i = 0; i < s.length(); i++) {
      set.add(s.charAt(i));
    }
    for (int i = 0; i < 26; i++) {
      char c1 = (char) ('Z' - i);
      char c2 = (char) ('z' - i);
      if (set.contains(c1) && set.contains(c2)) {
        return String.valueOf(c1);
      }
    }
    return "";
  }

  public String greatestLetter(String s) {
    int upperCaseCode = 0;
    int lowerCaseCode = 0;
    char c;
    for (int i = 0; i < s.length(); i++) {
      c = s.charAt(i);
      if (c > 'Z') {
        lowerCaseCode |= (1 << (c - 'a'));
      } else {
        upperCaseCode |= (1 << (c - 'A'));
      }
    }
    int results = (lowerCaseCode & upperCaseCode);
    int len = -1;
    while (results > 0) {
      results = results >> 1;
      len++;
    }
    return len == -1 ? "" : String.valueOf((char) ('A' + len));
  }

  // 2315. 统计星号
  public int countAsterisks(String s) {
    String[] strings = s.split("\\|");
    int count = 0;
    for (int i = 0; i < strings.length; i += 2) {
      count += (countEach(strings[i]));
    }
    return count;
  }

  private int countEach(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
      if (s.charAt(i) == '*') {
        count++;
      }
    }
    return count;
  }

  // 1669. 合并两个链表
  public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
    ListNode result = list1;
    ListNode curr = list1;
    int i = 0;
    while (curr != null && i < a - 1) {
      curr = curr.next;
      i++;
    }
    ListNode pre = curr;
    while (curr != null && i <= b) {
      curr = curr.next;
      i++;
    }
    ListNode next = curr;
    if (a == 0) {
      result = list2;
    } else {
      pre.next = list2;
    }
    if (next != null) {
      curr = list2;
      while (curr.next != null) {
        curr = curr.next;
      }
      curr.next = next;
    }
    return result;
  }

  // 119. 杨辉三角 II
  public List<Integer> getRow(int rowIndex) {
    List<Integer> result = new ArrayList<>(rowIndex + 1);
    result.add(1);
    int lastIndex;
    if ((rowIndex & 1) == 1) {
      lastIndex = ((rowIndex + 1) >> 1);
      for (int i = 1; i < lastIndex; i++) {
        result.add(C2(result.get(i - 1), rowIndex, i));
      }
    } else {
      lastIndex = (rowIndex >> 1);
      for (int i = 1; i <= lastIndex; i++) {
        result.add(C2(result.get(i - 1), rowIndex, i));
      }
    }
    for (int i = lastIndex - 1; i >= 0; i--) {
      result.add(result.get(i));
    }
    return result;
  }

  // 组合数公式-常规算法
  private int C(int n, int m) {
    int up = 1;
    for (int i = 0; i < m; i++) {
      up *= n;
      n--;
    }
    int down = 1;
    for (int i = 1; i <= m; i++) {
      down *= i;
    }
    return up / down;
  }

  // 组合数公式-迭代算法
  private int C2(int pre, int n, int m) {
    return (int) (((long) pre * (n - m + 1)) / m);
  }

  // 118. 杨辉三角
  public List<List<Integer>> generate(int numRows) {
    List<Integer> firstRow = Collections.singletonList(1);
    if (numRows == 1) {
      return Collections.singletonList(firstRow);
    }
    List<List<Integer>> result = new ArrayList<>();
    result.add(firstRow);
    for (int i = 1; i < numRows; i++) {
      result.add(generateRow(result.get(i - 1)));
    }
    return result;
  }

  private List<Integer> generateRow(List<Integer> preRow) {
    int size = preRow.size();
    List<Integer> result = new ArrayList<>(size + 1);
    result.add(0);
    result.addAll(preRow);
    for (int i = 0; i < size; i++) {
      result.set(i, preRow.get(i) + result.get(i));
    }
    return result;
  }

  // 88. 合并两个有序数组
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    int maxIndex = (m + n - 1);
    int i = m - 1, j = n - 1;
    while (i >= 0 && j >= 0) {
      if (nums1[i] < nums2[j]) {
        nums1[maxIndex] = nums2[j];
        j--;
      } else {
        nums1[maxIndex] = nums1[i];
        i--;
      }
      maxIndex--;
    }
    if (j >= 0) {
      System.arraycopy(nums2, 0, nums1, 0, j + 1);
    }
  }

  // 83. 删除排序链表中的重复元素
  public ListNode deleteDuplicates(ListNode head) {
    if (head == null) {
      return null;
    }
    Set<Integer> set = new HashSet<>();
    ListNode node = new ListNode(head.val);
    set.add(head.val);
    ListNode tmp = head.next;
    ListNode tail = node;
    ListNode newNode;
    while (tmp != null) {
      if (!set.contains(tmp.val)) {
        set.add(tmp.val);
        newNode = new ListNode(tmp.val);
        tail.next = newNode;
        tail = newNode;
      }
      tmp = tmp.next;
    }
    return node;
  }

  // 70. 爬楼梯
  public int climbStairs(int n) {
    if (n == 1 || n == 2) {
      return n;
    }
    int one = 1, two = 2, i = 3;
    int res;
    while (true) {
      res = one + two;
      if (++i > n) {
        break;
      }
      one = two;
      two = res;
    }
    return res;
  }

  // 69. x 的平方根
  public int mySqrt(int x) {
    if (x == 0 || x == 1) {
      return x;
    }
    double e = 0.0000005;
    double start = x;
    double next;
    while (true) {
      next = (start + x / start) / 2;
      if (Math.abs(start - next) < e) {
        break;
      }
      start = next;
    }
    return (int) start;
  }

  // 1817. 查找用户活跃分钟数
  public int[] findingUsersActiveMinutes(int[][] logs, int k) {
    Map<Integer, Set<Integer>> map = new HashMap<>();
    int userId;
    int timeMinute;
    Set<Integer> set;
    for (int[] log : logs) {
      userId = log[0];
      timeMinute = log[1];
      set = map.get(userId);
      if (set == null) {
        map.put(userId, new HashSet<>(Collections.singletonList(timeMinute)));
        continue;
      }
      set.add(timeMinute);
    }
    int[] result = new int[k];
    for (Set<Integer> value : map.values()) {
      int size = value.size();
      result[size - 1]++;
    }
    return result;
  }

  // 2299. 强密码检验器 II
  public boolean strongPasswordCheckerII(String password) {
    int len = password.length();
    if (len < 8) {
      return false;
    }
    boolean lestLowerCase = false;
    boolean lestUpperCase = false;
    boolean lestNumberChar = false;
    boolean lestSpecialChar = false;
    Set<Character> specialChars = new HashSet<>();
    specialChars.add('!');
    specialChars.add('@');
    specialChars.add('#');
    specialChars.add('$');
    specialChars.add('%');
    specialChars.add('^');
    specialChars.add('&');
    specialChars.add('*');
    specialChars.add('(');
    specialChars.add(')');
    specialChars.add('-');
    specialChars.add('+');
    char pre = password.charAt(0);
    char curr;
    for (int i = 0; i < len; i++) {
      curr = password.charAt(i);
      if (i > 0 && curr == pre) {
        return false;
      }
      if (!lestLowerCase && curr >= 'a' && curr <= 'z') {
        lestLowerCase = true;
      }
      if (!lestUpperCase && curr >= 'A' && curr <= 'Z') {
        lestUpperCase = true;
      }
      if (!lestNumberChar && curr > '0' && curr < '9') {
        lestNumberChar = true;
      }
      if (!lestSpecialChar && specialChars.contains(curr)) {
        lestSpecialChar = true;
      }
      pre = curr;
    }
    return lestLowerCase && lestUpperCase && lestNumberChar && lestSpecialChar;
  }

  public int countNicePairsTop(int[] nums) {
    final int MOD = 1000000007;
    int res = 0;
    Map<Integer, Integer> h = new HashMap<>();
    for (int i : nums) {
      int temp = i, j = 0;
      while (temp > 0) {
        j = j * 10 + temp % 10;
        temp /= 10;
      }
      int diff = i - j;
      Integer orDefault = h.getOrDefault(diff, 0);
      res = (res + orDefault) % MOD;
      h.put(diff, orDefault + 1);
    }
    return res;
  }

  public int countNicePairs(int[] nums) {
    Map<Integer, Integer> cache = new HashMap<>(nums.length);
    int diff;
    int total = 0;
    for (int num : nums) {
      diff = num - rev(num);
      Integer already = cache.getOrDefault(diff, 0);
      total = (total + already) % MOD;
      cache.put(diff, already + 1);
    }
    return total;
  }

  private int rev(int x) {
    int result = 0;
    while (x > 0) {
      result = (result * 10 + x % 10);
      x /= 10;
    }
    return result;
  }

  // 2293. 极大极小游戏
  public int minMaxGame(int[] nums) {
    int n = nums.length;
    if (n == 1) {
      return nums[0];
    }
    int newLength = n >> 1;
    int[] newNums = new int[newLength];
    for (int i = 0; i < newLength; i++) {
      if ((i & 1) == 0) {
        newNums[i] = Math.min(nums[2 * i], nums[2 * i + 1]);
        continue;
      }
      newNums[i] = Math.max(nums[2 * i], nums[2 * i + 1]);
    }
    return minMaxGame(newNums);
  }

  public int rearrangeCharacters(String s, String target) {
    Map<Character, Integer> sMap = sToMap(s);
    Map<Character, Integer> tMap = sToMap(target);
    return doHandle(sMap, tMap);
  }

  private int doHandle(Map<Character, Integer> sMap, Map<Character, Integer> tMap) {
    Set<Character> tKeys = tMap.keySet();
    Integer sCount;
    Integer tCount;
    int result = -1;
    int currCount;
    for (Character k : tKeys) {
      sCount = sMap.get(k);
      tCount = tMap.get(k);
      if (sCount == null || sCount < tCount) {
        return 0;
      }
      currCount = sCount / tCount;
      if (result == -1 || currCount < result) {
        result = currCount;
      }
    }
    return result;
  }

  public int rearrangeCharacters1(String s, String target) {
    try {
      return CompletableFuture.supplyAsync(() -> sToMap(s))
        .thenCombine(CompletableFuture.supplyAsync(() -> sToMap(target)), this::doHandle)
        .get();
    } catch (Exception e) {
      return 0;
    }
  }

  public String evaluate(String s, List<List<String>> knowledge) {
    Map<String, String> map = new HashMap<>();
    for (List<String> strings : knowledge) {
      map.put(strings.get(0), strings.get(1));
    }
    StringBuilder builder = new StringBuilder();
    char[] charArray = s.toCharArray();
    StringBuilder sb;
    int j;
    for (int i = 0; i < charArray.length; ) {
      if (charArray[i] == '(') {
        sb = new StringBuilder();
        for (j = (i + 1); ; j++) {
          if (charArray[j] == ')') {
            break;
          }
          sb.append(charArray[j]);
        }
        builder.append(map.getOrDefault(sb.toString(), "?"));
        i = (j + 1);
        continue;
      }
      builder.append(charArray[i]);
      i++;
    }
    return builder.toString();
  }

  public boolean digitCount(String num) {
    byte[] bytes = num.getBytes(StandardCharsets.UTF_8);
    int len = bytes.length;
    Map<Integer, Integer> map = new HashMap<>();
    for (byte b : bytes) {
      map.compute(b - 48, (k, v) -> v == null ? 1 : v + 1);
      if (map.get(b - 48) >= len) {
        return false;
      }
    }
    for (int i = 0; i < len; i++) {
      if (map.getOrDefault(i, 0) != (bytes[i] - 48)) {
        return false;
      }
    }
    return true;
  }

  // 1710. 卡车上的最大单元数
  public int maximumUnits(int[][] boxTypes, int truckSize) {
    int sum = 0;
    int typeCount = 0;
    int diff;
    Arrays.sort(boxTypes, (o1, o2) -> Integer.compare(o2[1], o1[1]));
    for (int[] typeArr : boxTypes) {
      diff = truckSize - typeCount;
      if (diff <= typeArr[0]) {
        sum += (diff * typeArr[1]);
        return sum;
      }
      typeCount += typeArr[0];
      sum += (typeArr[0] * typeArr[1]);
    }
    return sum;
  }

  // 1684. 统计一致字符串的数目
  public int countConsistentStrings(String allowed, String[] words) {
    int allowedMask = stringToMaskCode(allowed);
    return ((int) Arrays.stream(words).map(this::stringToMaskCode).filter(m -> (allowedMask | m) == allowedMask).count());
  }

  public void setZeroes(int[][] matrix) {
    Set<Integer> zeroRows = new HashSet<>();
    Set<Integer> zeroColumns = new HashSet<>();
    int rowLen = matrix.length;
    int colLen = matrix[0].length;
    for (int i = 0; i < rowLen; i++) {
      for (int j = 0; j < colLen; j++) {
        if (matrix[i][j] == 0) {
          zeroRows.add(i);
          zeroColumns.add(j);
        }
      }
    }
    for (Integer i : zeroRows) {
      Arrays.fill(matrix[i], 0);
    }
    for (int i = 0; i < rowLen; i++) {
      for (Integer j : zeroColumns) {
        matrix[i][j] = 0;
      }
    }
  }

  public boolean isFlipedString(String s1, String s2) {
    return s1.length() == s2.length() && (s1 + s1).contains(s2);
  }

  public int[] missingTwo(int[] nums) {
    // 000
    // 001
    // 010 √
    // 011 √
    // 100
    int res = 0;
    for (int n : nums) {
      res ^= n;
    }
    for (int n : build(nums.length + 2)) {
      res ^= n;
    }
    return nums;
  }

  private int[] build(int len) {
    int[] arr = new int[len];
    for (int i = 0; i < len; i++) {
      arr[i] = i + 1;
    }
    return arr;
  }

  public boolean checkPermutation1(String s1, String s2) {
    int len1 = s1.length();
    int len2 = s2.length();
    char[] total = new char[len1 + len2];
    System.arraycopy(s1.toCharArray(), 0, total, 0, len1);
    System.arraycopy(s2.toCharArray(), 0, total, len1, len2);
    int result = total[0];
    for (int i = 1; i < total.length; i++) {
      result ^= total[i];
    }
    return result == 0;
  }

  public boolean checkPermutation(String s1, String s2) {
    if (s1.length() != s2.length()) {
      return false;
    }
    return mapEquals(sToMap(s1), sToMap(s2));
  }

  private boolean mapEquals(Map<Character, Integer> map1, Map<Character, Integer> map2) {
    return map1.entrySet().parallelStream().allMatch(e -> Objects.equals(map2.get(e.getKey()), e.getValue()));
  }

  public boolean canPartitionKSubsets(int[] nums, int k) {
    int totalSum = Arrays.stream(nums).sum();
    int eachSum = totalSum / k;
    if (eachSum * k < totalSum) {
      return false;
    }
    int len = nums.length;
    Arrays.sort(nums);
    return false;
  }

  // 66. 加一
  public int[] plusOne(int[] digits) {
    int endIndex = digits.length - 1;
    int lastNum = digits[endIndex];
    if (lastNum != 9) {
      digits[endIndex] = lastNum + 1;
      return digits;
    }
    digits[endIndex] = 0;
    for (int index = endIndex - 1; index >= 0; index--) {
      if (digits[index] != 9) {
        digits[index] = digits[index] + 1;
        return digits;
      }
      digits[index] = 0;
    }
    int[] ints = new int[digits.length + 1];
    ints[0] = 1;
    return ints;
  }

  // 58. 最后一个单词的长度
  public int lengthOfLastWord1(String s) {
    int lastIndex = s.length() - 1;
    char[] chars = s.toCharArray();
    int count = 0;
    boolean flag = false;
    char c;
    for (int index = lastIndex; index >= 0; index--) {
      c = chars[index];
      if (c == ' ') {
        if (flag) {
          break;
        }
        continue;
      }
      flag = true;
      count++;
    }
    return count;
  }

  public int lengthOfLastWord(String s) {
    int index = s.length() - 1;
    char[] chars = s.toCharArray();
    for (; index >= 0; index--) {
      if (chars[index] != ' ') {
        break;
      }
    }
    int count = 0;
    for (; index >= 0; index--) {
      if (chars[index] == ' ') {
        break;
      }
      count++;
    }
    return count;
  }

  // 35. 搜索插入位置
  public int searchInsert(int[] nums, int target) {
    int left = 0, right = nums.length - 1, middle = (left + right) >> 1;
    if (nums[left] == target) {
      return left;
    }
    if (nums[middle] == target) {
      return middle;
    }
    if (nums[right] == target) {
      return right;
    }
    while (right - left > 1) {
      if (nums[middle] > target) {
        right = middle;
        middle = (left + right) >> 1;
      } else if (nums[middle] < target) {
        left = middle;
        middle = (left + right) >> 1;
      }
      if (nums[middle] == target) {
        return middle;
      }
    }
    return target < nums[left] ? left : (target > nums[right] ? right + 1 : right);
  }

  // 1636. 按照频率将数组升序排序
  public int[] frequencySort(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int n : nums) {
      map.put(n, map.getOrDefault(n, 0) + 1);
    }
    Comparator<Integer> comparator = (o1, o2) -> {
      int compare = map.get(o1) - map.get(o2);
      return compare == 0 ? (o2 - o1) : compare;
    };
    int len = nums.length;
    Integer[] integers = new Integer[len];
    for (int i = 0; i < len; i++) {
      integers[i] = nums[i];
    }
    Arrays.sort(integers, comparator);
    for (int i = 0; i < len; i++) {
      nums[i] = integers[i];
    }
    return nums;
  }

  public int flipLights(int n, int presses) {
    if (presses == 0) {
      return 1;
    }
    byte[] lights = new byte[n];
    Set<byte[]> set = new TreeSet<>(Arrays::compare);
    set.add(btn1(lights));
    set.add(btn2(lights));
    set.add(btn3(lights));
    set.add(btn4(lights));

    for (int i = 1; i < presses; i++) {
      for (byte[] bytes : set) {
        set.add(btn1(bytes));
        set.add(btn2(bytes));
        set.add(btn3(bytes));
        set.add(btn4(bytes));
      }
    }
    set.forEach(bs -> System.out.println(Arrays.toString(bs)));
    return set.size();
  }

  private byte[] btn1(byte[] lights) {
    return clickButton(lights, n -> true);
  }

  private byte[] btn2(byte[] lights) {
    return clickButton(lights, n -> (n & 1) == 0);
  }

  private byte[] btn3(byte[] lights) {
    return clickButton(lights, n -> (n & 1) == 1);
  }

  private byte[] btn4(byte[] lights) {
    return clickButton(lights, n -> (n - 1) % 3 == 0);
  }

  private byte[] clickButton(byte[] lights, Function<Integer, Boolean> condition) {
    int len = lights.length;
    byte[] copy = Arrays.copyOf(lights, len);
    for (int i = 0; i < len; i++) {
      if (condition.apply(i + 1)) {
        copy[i] = convertBit(copy[i]);
      }
    }
    return copy;
  }

  private byte convertBit(byte b) {
    if (b == 0) {
      return 1;
    }
    return 0;
  }

  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int[] indices = figureIndex(nums1.length + nums2.length);
    return mergeOrderedArray(nums1, nums2, indices[0], indices[1]);
  }

  private int[] figureIndex(int length) {
    if ((length & 1) == 0) {
      int half = length / 2;
      return new int[]{half - 1, half};
    }
    int half = (length - 1) / 2;
    return new int[]{half, half};
  }

  private double mergeOrderedArray(int[] nums1, int[] nums2, int m, int n) {
    int len1 = nums1.length;
    int len2 = nums2.length;
    int finalIndex = (n + 1);
    int[] mergedArray = new int[finalIndex];
    int i = 0, j = 0, index = 0;

    while (i < len1 && j < len2 && index < finalIndex) {
      if (nums1[i] <= nums2[j]) {
        mergedArray[index++] = nums1[i];
        i++;
      } else {
        mergedArray[index++] = nums2[j];
        j++;
      }
    }
    if (i == len1) {
      while (j < len2 && index < finalIndex) {
        mergedArray[index++] = nums2[j];
        j++;
      }
    }
    if (j == len2) {
      while (i < len1 && index < finalIndex) {
        mergedArray[index++] = nums1[i];
        i++;
      }
    }
    return (mergedArray[m] + mergedArray[n]) / 2.0;
  }

  public double trimMean(int[] arr) {
    int len = arr.length;
    int count = (int) (len * 0.05);
    double sum = 0;
    Arrays.sort(arr);
    for (int i = count; i < (len - count); i++) {
      System.out.println(arr[i]);
      sum += arr[i];
    }
    return sum / (len - 2 * count);
  }

  public int maxIncreaseKeepingSkyline1(int[][] grid) {
    int size = grid.length;
    int[] colMax = new int[size];
    int currRowMax = 0;
    int currColMax = 0;
    int result = 0;

    for (int i = 0; i < size; i++) {
      currRowMax = Arrays.stream(grid[i]).max().getAsInt();
      if (i == 0) {
        for (int j = 0; j < size; j++) {
          final int j1 = j;
          currColMax = Arrays.stream(grid).map(ints -> ints[j1]).max(Integer::compare).get();
          colMax[j] = currColMax;
          result += (Math.min(currRowMax, currColMax) - grid[i][j]);
        }
        continue;
      }
      for (int j = 0; j < size; j++) {
        result += (Math.min(currRowMax, colMax[j]) - grid[i][j]);
      }
    }
    return result;
  }

  public int maxIncreaseKeepingSkyline(int[][] grid) {
    int size = grid.length;
    int[] rowMax = new int[size];
    int[] colMax = new int[size];
    int result = 0;

    for (int i = 0; i < size; i++) {
      for (int j = 0; j < size; j++) {
        rowMax[i] = Math.max(rowMax[i], grid[i][j]);
        colMax[j] = Math.max(colMax[j], grid[i][j]);
      }
    }

    for (int i = 0; i < size; i++) {
      for (int j = 0; j < size; j++) {
        result += (Math.min(rowMax[i], colMax[j]) - grid[i][j]);
      }
    }
    return result;
  }

  public int maximumSwap(int num) {
    int[] nums = numAndArray(num);
    for (int i = 0; i < nums.length - 1; i++) {
      int j = maxValIndex(nums, i);
      if (j == i || nums[i] == nums[j]) {
        continue;
      }
      doSwap(nums, i, j);
      return numAndArray(nums);
    }
    return num;
  }

  private int maxValIndex(int[] nums, int start) {
    int maxValIndex = start;
    for (int i = start + 1; i < nums.length; i++) {
      if (nums[i] < nums[maxValIndex]) {
        continue;
      }
      maxValIndex = i;
    }
    return maxValIndex;
  }

  private int[] numAndArray(int num) {
    char[] chars = String.valueOf(num).toCharArray();
    int len = chars.length;
    int[] ints = new int[len];
    for (int i = 0; i < len; i++) {
      ints[i] = chars[i] - 48;
    }
    return ints;
  }

  private int numAndArray(int[] nums) {
    return Integer.parseInt(Arrays.stream(nums).mapToObj(String::valueOf).collect(Collectors.joining()));
  }

  private void doSwap(int[] nums, int index1, int index2) {
    int tmp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = tmp;
  }

  private int stringToMaskCode(String s) {
    int mask = 0;
    int len = s.length();
    for (int i = 0; i < len; i++) {
      mask |= (1 << (s.charAt(i) - 'a'));
    }
    return mask;
  }

  private Map<Character, Integer> sToMap(String s) {
    Map<Character, Integer> map = new HashMap<>();
    for (char c : s.toCharArray()) {
      map.put(c, map.getOrDefault(c, 0) + 1);
    }
    return map;
  }

  private int[] toArray(Collection<Integer> set) {
    int[] ints = new int[set.size()];
    int i = 0;
    for (Integer n : set) {
      ints[i++] = n;
    }
    return ints;
  }

  private int hammingWeight(int n) {
    int k = n;
    int count = 0;
    while (k != 0) {
      k &= (k - 1);
      count++;
    }
    return count;
  }
}
